// だれかおれをたすけてくれ!!! #include using namespace std; using int64 = long long; const int mod = 1e9 + 7; // const int mod = 998244353; const int64 infll = (1LL << 62) - 1; const int inf = (1 << 30) - 1; struct IoSetup { IoSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } } iosetup; template< typename T1, typename T2 > ostream &operator<<(ostream &os, const pair< T1, T2 > &p) { os << p.first << " " << p.second; return os; } template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; } template< typename T > ostream &operator<<(ostream &os, const vector< T > &v) { for(int i = 0; i < (int) v.size(); i++) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } template< typename T > istream &operator>>(istream &is, vector< T > &v) { for(T &in: v) is >> in; return is; } template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } template< typename T = int64 > vector< T > make_v(size_t a) { return vector< T >(a); } template< typename T, typename... Ts > auto make_v(size_t a, Ts... ts) { return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...)); } template< typename T, typename V > typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) { t = v; } template< typename T, typename V > typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) { for(auto &e: t) fill_v(e, v); } template< typename F > struct FixPoint : F { FixPoint(F &&f) : F(forward< F >(f)) {} template< typename... Args > decltype(auto) operator()(Args &&... args) const { return F::operator()(*this, forward< Args >(args)...); } }; template< typename F > inline decltype(auto) MFP(F &&f) { return FixPoint< F >{forward< F >(f)}; } /** * @brief Binary-Indexed-Tree(BIT) * @docs docs/binary-indexed-tree.md */ template< typename T > struct BinaryIndexedTree { private: vector< T > data; public: BinaryIndexedTree() = default; explicit BinaryIndexedTree(size_t sz) : data(sz + 1, 0) {} explicit BinaryIndexedTree(const vector< T > &vs) : data(vs.size() + 1, 0) { for(size_t i = 0; i < vs.size(); i++) data[i + 1] = vs[i]; for(size_t i = 1; i < data.size(); i++) { size_t j = i + (i & -i); if(j < data.size()) data[j] += data[i]; } } void add(int k, const T &x) { for(++k; k < (int) data.size(); k += k & -k) data[k] += x; } T fold(int r) const { T ret = T(); for(; r > 0; r -= r & -r) ret += data[r]; return ret; } T fold(int l, int r) const { return fold(r) - fold(l); } int lower_bound(T x) const { int i = 0; for(int k = 1 << (__lg(data.size() - 1) + 1); k > 0; k >>= 1) { if(i + k < data.size() && data[i + k] < x) { x -= data[i + k]; i += k; } } return i; } int upper_bound(T x) const { int i = 0; for(int k = 1 << (__lg(data.size() - 1) + 1); k > 0; k >>= 1) { if(i + k < data.size() && data[i + k] <= x) { x -= data[i + k]; i += k; } } return i; } }; const int MAX_V = 4e5; int main() { int N; cin >> N; vector< int > A(N), B(N); cin >> A >> B; for(auto &a: A) --a; for(auto &a: B) --a; int64 ret = 0; vector< int > latte(MAX_V), malta(MAX_V); vector< int > lp(MAX_V, inf), rp(MAX_V, inf); vector< int > pl(MAX_V, -inf), pr(MAX_V, -inf); vector< int > S(N); BinaryIndexedTree< int > bit(N); MFP([&](auto rec, int l, int r) -> void { if(l + 1 >= r) { ret += A[l] == B[l]; return; } int m = (l + r) / 2; rec(l, m); rec(m, r); { for(int k = r - 1; k >= m; k--) { lp[A[k]] = k; rp[B[k]] = k; } multiset< int > uku; for(int k = m - 1; k >= l; k--) { if(not latte[A[k]]) { latte[A[k]] = true; if(not malta[A[k]]) { uku.emplace(rp[A[k]]); } else { assert(uku.find(lp[A[k]]) != uku.end()); uku.erase(uku.find(lp[A[k]])); } } if(not malta[B[k]]) { malta[B[k]] = true; if(not latte[B[k]]) { uku.emplace(lp[B[k]]); } else { assert(uku.find(rp[B[k]]) != uku.end()); uku.erase(uku.find(rp[B[k]])); } } S[k] = uku.empty() ? m : *uku.rbegin(); } for(int k = r - 1; k >= m; k--) { lp[A[k]] = inf; rp[B[k]] = inf; } for(int k = m - 1; k >= l; k--) { latte[A[k]] = false; malta[B[k]] = false; } } { for(int k = l; k < m; k++) { pl[A[k]] = k; pr[B[k]] = k; } multiset< int > uku; for(int k = m; k < r; k++) { if(not latte[A[k]]) { latte[A[k]] = true; if(not malta[A[k]]) { uku.emplace(pr[A[k]]); } else { assert(uku.find(pl[A[k]]) != uku.end()); uku.erase(uku.find(pl[A[k]])); } } if(not malta[B[k]]) { malta[B[k]] = true; if(not latte[B[k]]) { uku.emplace(pl[B[k]]); } else { assert(uku.find(pr[B[k]]) != uku.end()); uku.erase(uku.find(pr[B[k]])); } } S[k] = uku.empty() ? m : *uku.begin(); } for(int k = l; k < m; k++) { pl[A[k]] = -inf; pr[B[k]] = -inf; } for(int k = m; k < r; k++) { latte[A[k]] = false; malta[B[k]] = false; } } vector< int > ord(m - l); iota(begin(ord), end(ord), l); sort(begin(ord), end(ord), [&](int a, int b) { return S[a] > S[b]; }); int p = r - 1; for(auto &a: ord) { while(p >= S[a]) { if(S[p] >= 0) { bit.add(S[p], 1); } --p; } ret += bit.fold(a, N); } while(++p < r) { if(S[p] >= 0) { bit.add(S[p], -1); } } })(0, N); cout << ret << endl; }