#![allow(unused_imports)] use std::cmp::*; use std::collections::*; use std::io::Write; use std::ops::Bound::*; #[allow(unused_macros)] macro_rules! debug { ($($e:expr),*) => { #[cfg(debug_assertions)] $({ let (e, mut err) = (stringify!($e), std::io::stderr()); writeln!(err, "{} = {:?}", e, $e).unwrap() })* }; } fn main() { let n = read::(); let mut a = read_vec::(); a.sort(); let b = read_vec::(); let mut comp = b.clone(); comp.append(&mut a.clone()); comp.sort(); comp.dedup(); let mut comp_dict = HashMap::new(); for i in 0..comp.len() { comp_dict.insert(comp[i], i); } let mut seg = SegTree::new(comp_dict.len(), 0i64, |a, b| a + b); let mut ans = 0; for i in 0..n { let b_pos = comp_dict[&b[i]]; let cur = seg.query(b_pos, b_pos + 1); seg.update(b_pos, cur + 1); let a_pos = comp_dict[&a[i]]; ans += seg.query(0, a_pos); } println!("{}", ans); } fn read() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } fn read_vec() -> Vec { read::() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } #[derive(Clone)] struct SegTree where F: Fn(T, T) -> T, T: std::clone::Clone + std::marker::Copy, { n: usize, dat: Vec, init: T, functor: F, } impl SegTree where F: Fn(T, T) -> T, T: std::clone::Clone + std::marker::Copy, { fn new(n: usize, init: T, f: F) -> SegTree { let mut m = 1; // For simplicity, we use 2 ** n sized SegTree. while m < n { m *= 2; } SegTree { n: m, dat: vec![init; 2 * m - 1], init: init, functor: f, } } // dat[k] = a; fn update(&mut self, k: usize, a: T) { let mut k = k; k += self.n - 1; self.dat[k] = a; while k > 0 { k = (k - 1) / 2; self.dat[k] = (self.functor)(self.dat[k * 2 + 1], self.dat[k * 2 + 2]); } } // [a, b) fn query(&self, a: usize, b: usize) -> T { self.query_inner(a, b, 0, 0, self.n) } fn query_inner(&self, a: usize, b: usize, k: usize, l: usize, r: usize) -> T { if r <= a || b <= l { return self.init; } if a <= l && r <= b { return self.dat[k]; } let vl = self.query_inner(a, b, k * 2 + 1, l, (l + r) / 2); let vr = self.query_inner(a, b, k * 2 + 2, (l + r) / 2, r); (self.functor)(vl, vr) } }