// #define NDEBUG #include #define REP_(i, a_, b_, a, b, ...) for (int i = (a), END_##i = (b); i < END_##i; ++i) #define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) #define ALL(x) std::begin(x), std::end(x) using Int = long long; using Uint = unsigned long long; using Real = long double; template inline bool chmax(T &a, U b) { return a < b and ((a = b), true); } template inline bool chmin(T &a, U b) { return a > b and ((a = b), true); } template constexpr T kBigVal = std::numeric_limits::max() / 2; #if __cplusplus < 202002L template inline int ssize(const T &a) { return (int) a.size(); } #endif struct CastInput { template operator T() const { T x; std::cin >> x; assert(bool(std::cin)); return x; } struct Sized { int n; template operator T() const { T xs(n); for (auto &x: xs) { std::cin >> x; assert(bool(std::cin)); } return xs; } }; Sized operator()(int n) const { return {n}; } } in; template std::ostream &out_seq(const Container &seq, const char *sep = " ", const char *ends = "\n", std::ostream &os = std::cout) { const auto itl = std::begin(seq), itr = std::end(seq); for (auto it = itl; it != itr; ++it) { if (it != itl) os << sep; os << *it; } return os << ends; } template std::ostream &out_one(const T &x, char endc) { if constexpr (std::is_same::value) { return std::cout << (x ? "Yes" : "No") << endc; } else { return std::cout << x << endc; } } template std::ostream &out(const T &x) { return out_one(x, '\n'); } template std::ostream &out(const T &head, Ts... tail) { return out_one(head, ' '), out(tail...); } void init_(bool interactive = false) { std::ios::sync_with_stdio(false); if (not interactive) std::cin.tie(nullptr); std::cout << std::fixed << std::setprecision(18); } void exit_() { #ifdef MY_DEBUG std::string _; assert((std::cin >> _).fail()); #endif std::cout.flush(), std::cerr.flush(), std::_Exit(0); } #ifdef MY_DEBUG #include "debug_dump.hpp" #include "backward.hpp" backward::SignalHandling kSignalHandling; #else #define DUMP(...) #define test_case(...) #define cerr if(false)cerr #endif template struct SegmentTree { using T = typename Monoid::T; int n_; // number of valid leaves. int offset_; // where leaves start std::vector data_; // data size: 2*offset_ inline int size() const { return n_; } inline int offset() const { return offset_; } explicit SegmentTree(int n) : n_(n) { offset_ = 1; while (offset_ < n_) offset_ <<= 1; data_.assign(2 * offset_, Monoid::id()); } explicit SegmentTree(const std::vector &leaves) : n_(leaves.size()) { offset_ = 1; while (offset_ < n_) offset_ <<= 1; data_.assign(2 * offset_, Monoid::id()); for (int i = 0; i < n_; ++i) { data_[offset_ + i] = leaves[i]; } for (int i = offset_ - 1; i > 0; --i) { data_[i] = Monoid::op(data_[i * 2], data_[i * 2 + 1]); } } // Sets i-th value (0-indexed) to x. void set(int i, const T &x) { int k = offset_ + i; data_[k] = x; // Update its ancestors. while (k > 1) { k >>= 1; data_[k] = Monoid::op(data_[k * 2], data_[k * 2 + 1]); } } // Queries by [l,r) range (0-indexed, half-open interval). T fold(int l, int r) const { l = std::max(l, 0) + offset_; r = std::min(r, offset_) + offset_; T vleft = Monoid::id(), vright = Monoid::id(); for (; l < r; l >>= 1, r >>= 1) { if (l & 1) vleft = Monoid::op(vleft, data_[l++]); if (r & 1) vright = Monoid::op(data_[--r], vright); } return Monoid::op(vleft, vright); } T fold_all() const { return data_[1]; } // Returns i-th value (0-indexed). T operator[](int i) const { return data_[offset_ + i]; } std::vector to_vec(int sz = -1) const { if (sz < 0 or sz > size()) sz = size(); std::vector res(sz); for (int i = 0; i < sz; ++i) res[i] = (*this)[i]; return res; } }; struct SumOp { using T = long long; static T op(const T &x, const T &y) { return x + y; // alt: saturating_add(x, y) } static constexpr T id() { return 0; } static T invert(const T &x) { return -x; } }; using namespace std; auto solve() { int n = in; vector A = in(n), B = in(n); vector ra(n), rb(n), C(n); REP(i, n) { --A[i]; --B[i]; ra[A[i]] = i; rb[B[i]] = i; } SegmentTree seg(n); Int inversion_count = 0; REP(i, n) { int j = ra[B[i]]; inversion_count += seg.fold(j + 1, n); seg.set(j, seg[j] + 1); } out(inversion_count); } int main() { init_(); const int T = 1;//in; REP(t, T) { test_case(t, T); (solve()); } exit_(); }