#ifndef _DEBUG #define _DEBUG #include __FILE__ signed main() { int N; cin >> N; vector A(N); for (int i = 0; i < N; i++) cin >> A.at(i), A.at(i)--; vector B(N); for (int i = 0; i < N; i++) cin >> B.at(i), B.at(i)--; cout << inv_count(A, B) << "\n"; } #else // #undef _DEBUG #pragma GCC diagnostic warning "-Wextra" #pragma GCC diagnostic warning "-Wshadow" #include using namespace std; template struct FenwickTree { private: int n; vector bit; public: FenwickTree() {} FenwickTree(int sz) : n(sz + 1), bit(n, 0) {} FenwickTree(const vector& v) : n(v.size() + 1), bit(n, 0) { for (int i = 0; i < n - 1; i++) add(i, v[i]); } void add(int i, T x) { i++; while (i < n) bit[i] += x, i += i & -i; } void add(int l, int r, T x) { add(l, x), add(r, -x); } T sum(int i) { i++; T ret = 0; while (i > 0) ret += bit[i], i -= i & -i; return ret; } T sum(int l, int r) { return sum(r - 1) - sum(l - 1); } T at(int i) { return sum(i, i + 1); } void print() { cout << "[FT/at]: {"; for (int i = 0; i < n; i++) { cout << at(i) << (i != n - 1 ? ", " : "}\n"); } cout << "[FT/cs]: {"; for (int i = 0; i < n; i++) { cout << sum(i) << (i != n - 1 ? ", " : "}\n"); } } }; long inv_count(const vector& u) { int n = u.size(); FenwickTree bt(n); long ans = 0; for (int i = 0; i < n; i++) { ans += i - bt.sum(u[i]); bt.add(u[i], 1); } return ans; } long inv_count(const vector& u, const vector& v) { int n = u.size(); vector> p(n); FenwickTree bt(n); for (int i = n - 1; i >= 0; --i) { p[u[i]].push_back(i); } long ans = 0; for (int i = 0; i < n; ++i) { int pos = p[v[i]].back(); p[v[i]].pop_back(); ans += pos - bt.sum(pos); bt.add(pos, 1); } return ans; } struct io_setup { io_setup() { cin.tie(nullptr)->sync_with_stdio(false); } } io_setup; template bool cmin(A& a, const B& b) { if (a > b) return a = b, true; return false; } template bool cmax(A& a, const B& b) { if (a < b) return a = b, true; return false; } template ostream& operator<<(ostream& os, const pair& p); template ostream& operator<<(ostream& os, const tuple& t); template ostream& operator<<(ostream& os, const tuple& t); #define foreach(it, a) for (auto it = a.begin(); it != a.end(); it++) ostream& operator<<(ostream& os, const vector& vec) { os << "{"; foreach (it, vec) { os << (it == vec.begin() ? "" : " ") << *it; } return os << "}"; } template ostream& operator<<(ostream& os, const vector& vec) { os << "{"; foreach (it, vec) { os << (it == vec.begin() ? "" : ", ") << *it; } return os << "}"; } template ostream& operator<<(ostream& os, const vector>& vec) { os << "{\n"; foreach (it, vec) { os << (it == vec.begin() ? " " : "\n ") << *it; } return os << "\n}"; } template ostream& operator<<(ostream& os, const vector>>& vec) { os << "{\n"; foreach (it, vec) { os << (it == vec.begin() ? "" : "\n") << it - vec.begin() << ": " << *it; } return os << "\n}"; } template ostream& operator<<(ostream& os, const set& se) { os << "{"; foreach (it, se) { os << (it == se.begin() ? "" : ", ") << *it; } return os << "}"; } template ostream& operator<<(ostream& os, const multiset& ms) { os << "{"; foreach (it, ms) { os << (it == ms.begin() ? "" : ", ") << *it; } return os << "}"; } template ostream& operator<<(ostream& os, const map& ma) { os << "{"; foreach (it, ma) { os << (it == ma.begin() ? "" : ", ") << *it; } return os << "}"; } template ostream& operator<<(ostream& os, priority_queue pq) { os << "{"; while (!pq.empty()) { os << pq.top(), pq.pop(); if (!pq.empty()) os << ", "; } return os << "}"; } template ostream& operator<<(ostream& os, const pair& p) { const auto& [a, b] = p; return os << "(" << a << ", " << b << ")"; } template ostream& operator<<(ostream& os, const tuple& t) { const auto& [a, b, c] = t; return os << "(" << a << ", " << b << ", " << c << ")"; } template ostream& operator<<(ostream& os, const tuple& t) { const auto& [a, b, c, d] = t; return os << "(" << a << ", " << b << ", " << c << ", " << d << ")"; } void dump_func() {} template void dump_func(const A& a, const B&... b) { cout << a << (sizeof...(b) ? ", " : "\n"); dump_func(b...); } #ifdef _DEBUG #define dump(...) cout << "[" << string(#__VA_ARGS__) << "]: ", dump_func(__VA_ARGS__) #else #define dump(...) #endif #endif