#include #include #include #include using namespace std; using T = vector; T op(const T& l, const T& r) { T merged; merged.reserve(l.size() + r.size()); for(auto x : l) merged.push_back(x); for(auto x : r) merged.push_back(x); sort(begin(merged), end(merged)); return merged; } using U = int; U count(const T& t, int v) { return end(t) - std::lower_bound(begin(t), end(t), v + 1); } struct SegmentTree { int n; vector tree; T id; SegmentTree(int _n, T _id) : n(_n), tree(2 * n, _id), id(_id) {} void update(int i, T val) { for(tree[i + n] = val, i = (i + n) / 2; i > 0; i /= 2) tree[i] = op(tree[2 * i], tree[2 * i + 1]); } U query(int l, int r, int v) { U lhs = 0, rhs = 0; for(l += n, r += n; l < r; l >>= 1, r >>= 1) { if(l & 1) lhs += count(tree[l++], v); if(!(r & 1)) rhs += count(tree[r--], v); } return lhs + rhs + (l == r ? count(tree[l], v) : 0); } }; int main() { int n; cin >> n; vector h(n), g(n); for(auto& x : h) cin >> x; for(auto& x : g) cin >> x; multimap hi, gi; for(int i = 0; i < n; ++i) { hi.insert({h[i], i}); gi.insert({g[i], i}); } vector perm(n); for(auto i = hi.begin(), j = gi.begin(); i != hi.end(); ++i, ++j) perm[i->second] = j->second; SegmentTree st(n, h); long long ans = 0; for(int i = 0; i < n; ++i) { auto j = perm[i]; // TODO: We can try different things here: // count between i and j of heights: // - more than h[i] // - more than max(h[i], h[j]) // - more than min(h[i], h[j]). // - between h[i] and h[j] // // I think none of these should work, in the end. ans += st.query(min(i, j) + 1, max(i, j) - 1, h[i]); } cout << ans << endl; }