// Author: Aquizahv #include <bits/stdc++.h> #define ll long long #define inf 0x3f3f3f3f #define lnf 0x3f3f3f3f using namespace std; const int N = 2e5 + 5, ND = N << 2; int n, m, x, a[N], b[N], ti, bti[N], ati[N], cnt; ll ans; pair<int, int> t[N]; vector<int> upd[N]; bool visa[N]; set<int> B; struct BIT { int t[N]; void add(int it, int x) { if (it <= 0) return; while (it <= m) { t[it] += x; it += it & -it; } } int sum(int it) { int res = 0; while (it > 0) { res += t[it]; it -= it & -it; } return res; } void update(int l, int r, int x) { // cout << l << ' ' << r << ' ' << x << endl; add(l, x), add(r + 1, -x); } int query(int it) { return it == 0 ? cnt : sum(it); } } f; struct disjoint_set { int f[N]; void init(int lmt) { for (int i = 1; i <= lmt; i++) f[i] = i; } int find(int idx) { if (f[idx] == idx) return idx; return f[idx] = find(f[idx]); } void merge(int u, int v) { int x = find(u), y = find(v); if (x != y) { if (ati[y] > ati[x]) swap(x, y); f[x] = y; } } } ds; #define lson (u + u) #define rson (u + u + 1) struct segtree { int mn[ND]; void pushup(int u) { mn[u] = min(mn[lson], mn[rson]); } void update(int u, int l, int r, int it, int x) { if (l == r) { mn[u] = x; return; } int mid = (l + r) >> 1; if (it <= mid) update(lson, l, mid, it, x); else update(rson, mid + 1, r, it, x); pushup(u); } int query(int u, int l, int r, int L, int R) { if (L <= l && r <= R) return mn[u]; if (R < l || r < L) return inf; int mid = (l + r) >> 1; return min(query(lson, l, mid, L, R), query(rson, mid + 1, r, L, R)); } } T; void add(int it) { // cout << it << endl; visa[it] = true; ati[it] = ti; if (!visa[it - 1] && !visa[it + 1]) f.update(1, ti - 1, 1), cnt++; else if (visa[it - 1] && visa[it + 1]) { f.update(1, ati[ds.find(it - 1)] - 1, -1); f.update(1, ati[ds.find(it + 1)] - 1, -1); ds.merge(it - 1, it + 1); ds.merge(it, it - 1); f.update(1, ati[ds.find(it)] - 1, 1); cnt--; } else if (visa[it - 1]) ds.merge(it, it - 1); else if (visa[it + 1]) ds.merge(it, it + 1); } int main() { cin >> n >> m >> x; B.insert(-1), B.insert(m + 2); for (int i = 1; i <= n; i++) scanf("%d", a + i), upd[a[i]].push_back(i); for (int i = 1; i <= m; i++) scanf("%d", b + i), t[i] = {x - b[i], i}, B.insert(i); sort(t + 1, t + m + 1); int j = 0; ds.init(n); memset(T.mn, 0x3f, sizeof(T.mn)); T.update(1, 0, m + 1, 0, 0); T.update(1, 0, m + 1, m + 1, 0); for (int i = 1; i <= m; i++) { ti++; int ib = t[i].second; bti[ib] = ti; B.erase(ib); T.update(1, 0, m + 1, ib, ti); // cout << t[i].second << ' ' << t[i].first << endl; while (j < 2e5 && j + 1 <= t[i].first) { j++; for (auto k : upd[j]) add(k); } // for (int i = 1; i <= n; i++) // cout << visa[i] << " \n"[i == n]; // cout << cnt << endl; auto it = B.lower_bound(ib); int r = (*it) - 1; int l = (*(--it)) + 1; int lmn = T.query(1, 0, m + 1, l, ib), rmn = T.query(1, 0, m + 1, ib, r); int mx = max(lmn, rmn); ans += f.query(mx); // cout << "---- " << l << ' ' << r << ' ' << lmn << ' ' << rmn << ' ' << mx << ' ' << f.query(mx) << endl; } cout << ans << endl; return 0; } /* x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x left first <= right first < */