// ---------- begin init array ---------- pub struct InitArray { data: Vec, used: Vec, list: Vec, zero: T, } impl InitArray { pub fn new(size: usize, zero: T) -> Self { InitArray { data: vec![zero; size], used: vec![false; size], list: vec![], zero: zero, } } pub fn init(&mut self) { for x in self.list.drain(..) { self.used[x] = false; self.data[x] = self.zero; } } } impl std::ops::Index for InitArray { type Output = T; fn index(&self, pos: usize) -> &Self::Output { &self.data[pos] } } impl std::ops::IndexMut for InitArray { fn index_mut(&mut self, pos: usize) -> &mut Self::Output { if !self.used[pos] { self.used[pos] = true; self.list.push(pos); } &mut self.data[pos] } } // ---------- end init array ---------- fn read() -> (i32, Vec) { let mut s = String::new(); use std::io::Read; std::io::stdin().read_to_string(&mut s).unwrap(); let mut it = s.trim().split_whitespace().flat_map(|s| s.parse::()); let mut next = || it.next().unwrap(); let n = next(); let k = next(); (k, (0..n).map(|_| next()).collect()) } fn run() { let (k, a) = read(); let mut z = a.clone(); z.extend(a.iter().map(|a| k - *a)); z.sort(); z.dedup(); let mut a = a.iter().map(|a| z.binary_search(a).unwrap()).collect::>(); let mut map = InitArray::new(z.len(), (0usize, 0usize)); let mut calc = |l: &[usize], r: &[usize]| -> usize { map.init(); let mut min = z.len(); let mut cnt = 0; let mut x = 0; let mut ans = 0; for (i, &r) in r.iter().enumerate() { if min > r { min = r; cnt = 1; } else if min == r { cnt += 1; } while l.get(x).map_or(false, |l| *l > min) { let po = &mut map[l[x]]; po.0 += 1; po.1 += x + 1; x += 1; } if cnt == 1 { let po = map[z.len() - 1 - r]; ans += po.0 * (i + 1) + po.1; } } ans }; let mut ans = 0; let mut dfs = vec![a.as_mut_slice()]; while let Some(a) = dfs.pop() { if a.len() == 1 { if a[0] == z.len() - 1 - a[0] { ans += 1; } continue; } let m = a.len() / 2; let (l, r) = a.split_at_mut(m); l.reverse(); ans += calc(l, r) + calc(r, l); dfs.push(l); dfs.push(r); } println!("{}", ans); } fn main() { run(); }