#include #include #include #include #include #include using namespace std; using T = long long; T op(T l, T r) { return max(l, r); } struct SegmentTree { int n; vector tree; T id; // Pass the identity here and to initialization using repeated updates. SegmentTree(int _n, T _id = -1e6) : n(_n + 1), tree(2 * n, _id), id(_id) {} void update(int i, T val) { ++i; for(tree[i + n] = val, i = (i + n) / 2; i > 0; i /= 2) tree[i] = op(tree[2 * i], tree[2 * i + 1]); } T query(int l, int r) { ++l, ++r; // [l, r] T lhs = T(id), rhs = T(id); for(l += n, r += n; l < r; l >>= 1, r >>= 1) { if(l & 1) lhs = op(lhs, tree[l++]); if(!(r & 1)) rhs = op(tree[r--], rhs); } return op(l == r ? op(lhs, tree[l]) : lhs, rhs); } // Find first element right of l with value >= k int findr(int l, T k) { l += n + 2; while(tree[l] < k) ++l /= 2; while(l <= n) if(tree[l *= 2] < k) ++l; return l - n - 1; } // Find first element left of r with value >= k int findl(int r, T k) { r += n; while(r > 1 and tree[r] < k) r = max(1, --r / 2); if(tree[r] < k) return -1; while(r <= n) if(tree[(r *= 2) + 1] >= k) ++r; return r - n - 1; } }; 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 r) const { // [0, r] 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() { 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), phi(n), pgi(n); iota(begin(ph), end(ph), 0); iota(begin(pg), end(pg), 0); // ph[i] and pg[i] indicate the position of the i'th smallest element in h and g. // phi[i] and pgi[i] indicate the index of g[i] in ph[i]. 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]; }); for(int i = 0; i < n; ++i) phi[ph[i]] = i, pgi[pg[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. vector dd(n); long long ans = 0; for(int k = 0; k < n; ++k) { // i moves to position j int i = ph[k], j = pg[k]; ht.update(i, 1); gt.update(j, 1); dd[i] = (i - ht.query(i)) - (j - gt.query(j)); ans += abs(dd[i]); } cout << ans << endl; // Now compute the moves. SegmentTree st(n); for(int i = 0; i < n;++i) st.update(i, h[i]); int moves = 0; auto make_swap = [&](int i, int j) { swap(dd[i], dd[j]); swap(h[i], h[j]); swap(phi[i], phi[j]); swap(ph[phi[i]], ph[phi[j]]); st.update(i, h[i]); st.update(j, h[j]); cout << i + 1 << ' ' << j + 1 << '\n'; if(++moves == 200'000) exit(0); }; while(moves < ans){ int k = rand() % n; // The k'th smallest value at position i needs to move to position j int i = ph[k], j = pg[k]; //cerr << "Move " << h[i] << " from " << i << " to " << j << " dd " << dd[i] << endl; while(dd[i] < 0){ // Find the first larger k element right of i. // Find the first i left of k. int k = st.findr(i, h[i]+1); if(k<0 or k >= n) break; int i2 = st.findl(k, h[i]); // Swap i2 and k. ++dd[i2]; make_swap(i2, k); if(i == i2) i = k; } // Same but mirrored. while(dd[i] > 0){ int k = st.findl(i, h[i]+1); if(k<0 or k >= n) break; int i2 = st.findr(k, h[i]); --dd[i2]; make_swap(i2, k); if(i == i2) i = k; } } }