#include using namespace std; using ll = long long; constexpr char newl = '\n'; template struct Nothing { using Tm = U; using To = V; static Tm merge(const Tm& x, const Tm& y) { return unit(); } static To op_merge(const To& x, const To& y) { return op_unit(); } static Tm apply(const Tm& vm, const To& vo, size_t seg_len) { return vm; } static constexpr Tm unit() { return Tm(0); } static constexpr To op_unit() { return To(0); } }; // [Related]: monoid_op // https://www.slideshare.net/iwiwi/2-12188757 // https://tubo28.me/compprog/algorithm/treap/ // https://ei1333.github.io/luzhiled/snippets/structure/rbst.html // https://qiita.com/tubo28/items/f058582e457f6870a800 template > class Treap { public: using Tm = typename MonoidOp::Tm; using To = typename MonoidOp::To; private: inline static unsigned int randxor() noexcept { static unsigned int x=123456789,y=362436069,z=521288629,w=88675123; unsigned int t; t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) ); } public: struct Node { unsigned int pri; size_t sz; Tm val, sum; To lazy; unique_ptr lch, rch; Node(const Tm& x) : pri(randxor()), sz(1), val(x), sum(x), lazy(MonoidOp::op_unit()) {} static constexpr size_t size(const unique_ptr& node) noexcept { return (!node ? 0 : node->sz); } static constexpr Tm getSum(const unique_ptr& node) noexcept { return (!node ? MonoidOp::unit() : node->sum); } }; private: inline static unique_ptr& update(unique_ptr& node) noexcept { node->sz = Node::size(node->lch) + Node::size(node->rch) + 1; node->sum = MonoidOp::merge(MonoidOp::merge(Node::getSum(node->lch), node->val), Node::getSum(node->rch)); return node; } inline static unique_ptr& push(unique_ptr& node) noexcept { if (node->lazy == MonoidOp::op_unit()) return update(node); node->val = MonoidOp::apply(node->val, node->lazy, 1); if (node->lch) { node->lch->lazy = MonoidOp::op_merge(node->lch->lazy, node->lazy); node->lch->sum = MonoidOp::apply(node->lch->sum, node->lazy, Node::size(node->lch)); } if (node->rch) { node->rch->lazy = MonoidOp::op_merge(node->rch->lazy, node->lazy); node->rch->sum = MonoidOp::apply(node->rch->sum, node->lazy, Node::size(node->rch)); } node->lazy = MonoidOp::op_unit(); return update(node); } // split into [0, pos), [pos, size(node)) static pair< unique_ptr, unique_ptr > split(unique_ptr node, size_t pos) noexcept { if (!node) return pair< unique_ptr, unique_ptr >(); assert(pos <= Node::size(node)); push(node); if (pos <= Node::size(node->lch)) { auto p = split(move(node->lch), pos); node->lch = move(p.second); return {move(p.first), move(update(node))}; } else { auto p = split(move(node->rch), pos - Node::size(node->lch) - 1); node->rch = move(p.first); return {move(update(node)), move(p.second)}; } } static unique_ptr merge(unique_ptr nodeL, unique_ptr nodeR) noexcept { if (!nodeR) return nodeL; if (!nodeL) return nodeR; if (nodeL->pri > nodeR->pri) { push(nodeL); nodeL->rch = merge(move(nodeL->rch), move(nodeR)); return move(update(nodeL)); } else { push(nodeR); nodeR->lch = merge(move(nodeL), move(nodeR->lch)); return move(update(nodeR)); } } static void insert(unique_ptr& node, size_t pos, const Tm& val) noexcept { auto p = split(move(node), pos); auto tmp = merge(move(p.first), move(unique_ptr(new Node(val)))); node = move(merge(move(tmp), move(p.second))); } static void erase(unique_ptr& node, size_t pos) noexcept { if (!node) return; assert(pos < Node::size(node)); auto pr = split(move(node), pos + 1); auto pl = split(move(pr.first), pos); node = merge(move(pl.first), move(pr.second)); } static void update(unique_ptr& node, size_t a, size_t b, const To& x) noexcept { auto p1 = split(move(node), b); auto p2 = split(move(p1.first), a); p2.second->lazy = MonoidOp::op_merge(p2.second->lazy, x); node = merge(merge(move(p2.first), move(push(p2.second))), move(p1.second)); } static Tm query(unique_ptr& node, size_t a, size_t b) noexcept { auto p1 = split(move(node), b); auto p2 = split(move(p1.first), a); Tm res = Node::getSum(p2.second); node = merge(merge(move(p2.first), move(p2.second)), move(p1.second)); return res; } static void set(unique_ptr& node, size_t pos, const Tm& x) { push(node); if (pos < Node::size(node->lch)) set(node->lch, pos, x); else if (pos == Node::size(node->lch)) node->val = x; else set(node->rch, pos - Node::size(node->lch) - 1, x); update(node); } static unique_ptr build(size_t l, size_t r, const vector& v) { if (l + 1 >= r) return unique_ptr(new Node(v[l])); return merge(build(l, (l + r) >> 1, v), build((l + r) >> 1, r, v)); } static void dump(unique_ptr& node) noexcept { if (!node) return; push(node); dump(node->lch); cerr << node->val << " "; dump(node->rch); } protected: unique_ptr root; private: Treap(unique_ptr& node) : root(move(node)) {} public: Treap() = default; Treap(size_t sz, const Tm& initial_value = MonoidOp::unit()) { vector v(sz, initial_value); root = build(0, sz, v); } Treap(const vector& v) { root = build(0, v.size(), v); } constexpr bool empty() const noexcept { return !root; } constexpr size_t size() const noexcept { return Node::size(root); } // // split into [0, pos), [pos, size()) // [WARNING!!!]: Don't use this Treap after split inline pair< Treap, Treap > split(size_t pos) noexcept { auto p = split(move(root), pos); return {Treap(p.first), Treap(p.second)}; } // merge tree from the right of this Treap // [WARNING!!!]: Don't use tree after merge inline void merge(Treap& tree) noexcept { root = merge(move(root), move(tree.root)); } inline void insert_at(size_t pos, const Tm& val) noexcept { insert(root, pos, val); } inline void erase_at(size_t pos) noexcept { erase(root, pos); } // [a, b) inline void update(size_t a, size_t b, const To& x) { update(root, a, b, x); } // [a, b) inline Tm query(size_t a, size_t b) noexcept { return query(root, a, b); } inline Tm get(size_t pos) noexcept { return query(pos, pos + 1); } inline void set(size_t pos, const Tm& x) { set(root, pos, x); } inline void dump() noexcept { cerr << "Seq: "; dump(root); cerr << newl; } }; // [Depends on]: Treap template class OrderedMultiSet : public Treap< Nothing > { public: using Tree = Treap< Nothing >; using Node = typename Tree::Node; private: static T at(const unique_ptr& node, size_t pos) noexcept { if (pos < Node::size(node->lch)) return at(node->lch, pos); if (pos == Node::size(node->lch)) return node->val; return at(node->rch, pos - Node::size(node->lch) - 1); } static size_t lower_bound(const unique_ptr& node, T val) noexcept { if (!node) return 0; if (val <= node->val) return lower_bound(node->lch, val); return lower_bound(node->rch, val) + Node::size(node->lch) + 1; } static size_t upper_bound(const unique_ptr& node, T val) noexcept { if (!node) return 0; if (val < node->val) return upper_bound(node->lch, val); return upper_bound(node->rch, val) + Node::size(node->lch) + 1; } static bool contains(const unique_ptr& node, T val) noexcept { if (!node) return false; if (val == node->val) return true; if (val < node->val) return contains(node->lch, val); else return contains(node->rch, val); } // Use these function only inside void insert_at(size_t, const typename Tree::Tm&); void erase_at(size_t); public: using Tree::Treap; // Note: https://qiita.com/matsumoto_sp/items/233503b4a31dc1f190b6 OrderedMultiSet() = default; OrderedMultiSet(const vector& v) : Tree::Treap(v) { assert(is_sorted(v.begin(), v.end())); } // Don't use these functions void update(size_t, size_t, const typename Tree::To&) = delete; typename Tree::Tm query(size_t, size_t, const typename Tree::To&) = delete; typename Tree::Tm get(size_t) = delete; void set(size_t, const typename Tree::Tm&) = delete; inline T at(size_t pos) noexcept { assert(pos < Tree::size()); return at(Tree::root, pos); } // return position (index) // if val doesn't exist, return size() inline size_t find(T val) noexcept { return (contains(val) ? lower_bound(val) : Tree::size()); } // return position (index) inline size_t lower_bound(T val) noexcept { return lower_bound(Tree::root, val); } // return position (index) inline size_t upper_bound(T val) noexcept { return upper_bound(Tree::root, val); } inline bool contains(T val) noexcept { return contains(Tree::root, val); } inline size_t count(T val) noexcept { return upper_bound(val) - lower_bound(val); } inline virtual void insert(T val) noexcept { Tree::insert_at(lower_bound(val), val); } inline void erase(T val) noexcept { if (!contains(val)) return; Tree::erase_at(lower_bound(val)); } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; vector a(n), b(n); for (int i = 0; i < n; i++) { cin >> a[i]; } sort(a.begin(), a.end()); for (int i = 0; i < n; i++) { cin >> b[i]; } OrderedMultiSet memo; ll ans = 0; for (int i = 0; i < n; i++) { memo.insert(b[i]); ans += memo.lower_bound(a[i]); } cout << ans << newl; return 0; }