#include #include #include #include using namespace std; template struct FenwickTree { // Use 0 based indices. int n; vector tree; FenwickTree(int n_) : n(n_ + 1) { tree.assign(n + 1, 0); } template FenwickTree(int n, F f) : n(n) { tree.assign(n + 1, 0); for(int b = 1; b <= n; b *= 2) for(int i = b; i <= n; i += 2 * b) { tree[i] += f(i - 1); if(i + b <= n) tree[i + b] += tree[i]; } } T query(int l, int r) { return query(r) - query(l - 1); } // [l, r] T query(int r) const { // [0, r] assert(r + 1 <= n); T s = 0; for(++r; r > 0; r -= (r & (-r))) s += tree[r]; return s; } void update(int i, T v) { for(++i; i <= n; i += (i & (-i))) tree[i] += v; } }; 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}); } FenwickTree ht(n), gt(n); // For each height h that moves from position i to j, compute the number of taller people to // the left of it. Add the difference to the answer. long long ans = 0; for(auto it = hi.rbegin(), jt = gi.rbegin(); it != hi.rend(); ++it, ++jt) { assert(it->first == jt->first); // i moves to position j int i = it->second; int j = jt->second; ht.update(i, 1); gt.update(j, 1); ans += abs(ht.query(i) - gt.query(j)); } cout << ans << endl; }