#include using namespace std; #define INF_LL (int64)1e18 #define INF (int32)1e9 #define REP(i, n) for(int64 i = 0;i < (n);i++) #define FOR(i, a, b) for(int64 i = (a);i < (b);i++) #define all(x) x.begin(),x.end() #define fs first #define sc second using int32 = int_fast32_t; using uint32 = uint_fast32_t; using int64 = int_fast64_t; using uint64 = uint_fast64_t; using PII = pair; using PLL = pair; const double eps = 1e-10; templateinline void chmin(A &a, B b){if(a > b) a = b;} templateinline void chmax(A &a, B b){if(a < b) a = b;} template vector make_v(size_t a){return vector(a);} template auto make_v(size_t a,Ts... ts){ return vector(ts...))>(a,make_v(ts...)); } template typename enable_if::value!=0>::type fill_v(U &u,const V... v){u=U(v...);} template typename enable_if::value==0>::type fill_v(U &u,const V... v){ for(auto &e:u) fill_v(e,v...); } template class #if defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard) [[nodiscard]] #endif // defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard) FixPoint final : private F { public: template explicit constexpr FixPoint(G&& g) noexcept : F{std::forward(g)} {} template constexpr decltype(auto) operator()(Args&&... args) const #if !defined(__GNUC__) || defined(__clang__) || __GNUC__ >= 9 noexcept(noexcept(F::operator()(std::declval(), std::declval()...))) #endif // !defined(__GNUC__) || defined(__clang__) || __GNUC__ >= 9 { return F::operator()(*this, std::forward(args)...); } }; // class FixPoint #if defined(__cpp_deduction_guides) template FixPoint(F&&) -> FixPoint>; #endif // defined(__cpp_deduction_guides) namespace { template #if !defined(__has_cpp_attribute) || !__has_cpp_attribute(nodiscard) # if defined(__GNUC__) && (__GNUC__ > 3 || __GNUC__ == 3 && __GNUC_MINOR__ >= 4) __attribute__((warn_unused_result)) # elif defined(_MSC_VER) && _MSC_VER >= 1700 && defined(_Check_return_) _Check_return_ # endif // defined(__GNUC__) && (__GNUC__ > 3 || __GNUC__ == 3 && __GNUC_MINOR__ >= 4) #endif // !defined(__has_cpp_attribute) || !__has_cpp_attribute(nodiscard) inline constexpr decltype(auto) makeFixPoint(F&& f) noexcept { return FixPoint>{std::forward>(f)}; } } // namespace template class Container=::std::vector> class LazySegTree{ public: using value_structure = ValueMonoid; using value_type = typename value_structure::value_type; using operator_structure = OperatorMonoid; using operator_type = typename operator_structure::value_type; using modifier = Modifier; using const_reference = const value_type &; using container_value_type = Container; using container_operator_type = Container; using size_type = typename container_value_type::size_type; private: container_value_type tree; container_operator_type lazy; size_type size_, height; static size_type getsize(const size_type x){ size_type ret = 1; while(ret < x) ret <<= 1; return ret; } static size_type getheight(const size_type x){ size_type ret = 0; while((static_cast(1) << ret) < x){ ret++; } return ret; } inline static value_type calc(const value_type a, const value_type b){ return value_structure::operation(a, b); } inline static void apply(operator_type &data, const operator_type a){ data = operator_structure::operation(data, a); } inline static value_type reflect(const value_type v, const operator_type o){ return modifier::operation(v, o); } void push(const size_type index){ tree[index] = reflect(tree[index], lazy[index]); apply(lazy[index << 1], lazy[index]); apply(lazy[index << 1 | 1], lazy[index]); lazy[index] = operator_structure::identity(); } void calc_node(const size_type index){ if(tree.size() <= (index << 1 | 1)) return; assert(0 < index); tree[index] = calc(reflect(tree[index << 1], lazy[index << 1]), reflect(tree[index << 1 | 1], lazy[index << 1 | 1])); } void build(size_type index){ while(index >>= 1){ calc_node(index); } } void propagate(const size_type index){ for(size_type shift = height; shift ; --shift){ push(index >> shift); } } void rebuild(){ for(size_type i = size_-1;i > 0;--i){ calc_node(i); } } public: LazySegTree() : size_(0), height(0), tree(), lazy(){} LazySegTree(const size_type size) : size_(size), height(getheight(size)), tree(size << 1, value_structure::initializer()), lazy(size << 1, operator_structure::identity()){ rebuild(); } template LazySegTree(InputIterator first, InputIterator last) : size_(::std::distance(first, last)){ height = getheight(size_); tree = container_value_type(size_, value_structure::identity()); lazy = container_operator_type(size_ << 1, operator_structure::identity()); tree.insert(tree.end(), first, last); rebuild(); } size_type size() const { return size_; } const_reference operator[](const size_type k){ assert(k < size_); propagate(k+size_); tree[k+size_] = reflect(tree[k+size_], lazy[k+size_]); lazy[k+size_] = operator_structure::identity(); return tree[k+size_]; } value_type query(size_type l, size_type r){ assert(l <= r); assert(0 <= l && l < size_); assert(0 <= r && r <= size_); value_type retl = value_structure::identity(), retr = value_structure::identity(); l += size_; r += size_; propagate(l); propagate(r-1); build(l); build(r-1); for(; l < r ; l >>= 1, r >>= 1){ if(l&1){ retl = calc(retl, reflect(tree[l], lazy[l])); l++; } if(r&1){ r--; retr = calc(reflect(tree[r], lazy[r]), retr); } } return calc(retl, retr); } void update(size_type l, size_type r, const operator_type& data){ assert(l <= r); assert(0 <= l && l < size_); assert(0 <= r && r <= size_); l += size_; r += size_; propagate(l); propagate(r - 1); for(size_type l_ = l, r_ = r; l_ < r_ ; l_ >>= 1, r_ >>= 1){ if(l_ & 1) apply(lazy[l_++], data); if(r_ & 1) apply(lazy[--r_], data); } build(l); build(r - 1); } template void update(size_type index, const F& f){ assert(0 <= index && index < size()); index += size_; propagate(index); tree[index] = f(::std::move(tree[index])); lazy[index] = operator_structure::identity(); build(index); } /* template size_type search(const F& f) const { // [0, result) is True and [0, result-1) is not. if(f(value_structure::identity())) return 0; if(!f(tree[1])) return size_+1; value_type acc = value_structure::identity(); size_type i = 1; while(i < } */ }; class v_monoid { public: using value_type = PLL; static const value_type identity() { return PLL(INF_LL, 0); } static const value_type initializer() { return identity(); } static const value_type operation(const value_type& a, const value_type& b) { if (a.fs < b.fs) return a; if (a.fs > b.fs) return b; return PLL(a.fs, a.sc + b.sc); } }; class o_monoid { public: using value_type = int64; static const value_type identity() { return 0; } static const value_type operation(const value_type& a, const value_type& b) { return a + b; } }; class modifier { public: static const PLL operation(const PLL& a, const int64& b) { return PLL(a.fs + b, a.sc); } }; int main(void){ cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; assert(1 <= N && N <= 200000); vector A(N), B(N); REP(i, N) { cin >> A[i]; assert(1 <= A[i] && A[i] <= 400000); } REP(i, N) { cin >> B[i]; assert(1 <= B[i] && B[i] <= 400000); } vector> Al(412345), Bl(412345); vector seg(412345, PLL(N, N)); vector v(N + 1, PLL(0, 1)); LazySegTree lsg(all(v)); REP(i, N) { Al[A[i]].push_back(i); Bl[B[i]].push_back(i); } auto add = [&](int64 i, int64 x) { auto [l, r] = minmax(seg[i].fs, seg[i].sc); lsg.update(l, r, x); }; REP(i, 412345) { if (Al[i].size()) seg[i].fs = Al[i][0]; if (Bl[i].size()) seg[i].sc = Bl[i][0]; add(i, 1); } int64 res = 0; REP(l, N) { auto ret = lsg.query(l, N); if (ret.fs == 0) res += ret.sc; add(A[l], -1); if (A[l] != B[l]) add(B[l], -1); seg[A[l]].fs = N; Al[A[l]].pop_front(); seg[B[l]].sc = N; Bl[B[l]].pop_front(); if (Al[A[l]].size()) seg[A[l]].fs = Al[A[l]][0]; if (Bl[B[l]].size()) seg[B[l]].sc = Bl[B[l]][0]; add(A[l], 1); if (A[l] != B[l]) add(B[l], 1); } cout << res << endl; }