#include #include #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() { // NOTE: This solution has fast IO, while the others don't. iostream::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector h(n), g(n); for(auto& x : h) cin >> x; for(auto& x : g) cin >> x; vector ph(n), pg(n); iota(begin(ph), end(ph), 0); iota(begin(pg), end(pg), 0); stable_sort(begin(ph), end(ph), [&](int i, int j) { return h[i] < h[j]; }); stable_sort(begin(pg), end(pg), [&](int i, int j) { return g[i] < g[j]; }); // ph[i] and pg[i] now indicate the position of the i'th smallest element in h and g. 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(int k = 0; k < n; ++k) { // i moves to position j int i = ph[k]; int j = pg[k]; ht.update(i, 1); gt.update(j, 1); ans += abs((i - ht.query(i)) - (j - gt.query(j))); } cout << ans << endl; }