use std::io::Read; use std::io::Write; use std::rc::Rc; type Link = Option>; struct Node { sum: i64, cnt: i64, left: Link, right: Link, } fn eval(t: &Link) -> (i64, i64) { match t.as_ref() { None => (0, 0), Some(ref t) => (t.sum, t.cnt), } } fn new_node(l: Link, r: Link) -> Link { let u = eval(&l); let v = eval(&r); Some(Rc::new(Node { sum: u.0 + v.0, cnt: u.1 + v.1, left: l, right: r, })) } fn find(t: &Link, l: usize, r: usize, x: usize, y: usize) -> (i64, i64) { if t.is_none() || r <= x || y <= l { return (0, 0); } let t = t.as_ref().unwrap(); if x <= l && r <= y { return (t.sum, t.cnt); } let m = (l + r) / 2; let (a, b) = find(&t.left , l, m, x, y); let (c, d) = find(&t.right, m, r, x, y); (a + c, b + d) } fn update(mut t: Link, l: usize, r: usize, x: usize, val: i64) -> Link { assert!(l <= x && x < r); if l + 1 == r { return Some(Rc::new(Node { sum: val, cnt: 1, left: None, right: None, })); } if t.is_none() { t = new_node(None, None); } let t = t.unwrap(); let m = (l + r) / 2; let (left, right) = if x < m { (update(t.left.clone(), l, m, x, val), t.right.clone()) } else { (t.left.clone(), update(t.right.clone(), m, r, x, val)) }; new_node(left, right) } fn run() { let out = std::io::stdout(); let mut out = std::io::BufWriter::new(out.lock()); let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); let mut it = s.trim().split_whitespace(); let n: usize = it.next().unwrap().parse().unwrap(); let q: usize = it.next().unwrap().parse().unwrap(); let a: Vec = (0..n).map(|_| it.next().unwrap().parse().unwrap()).collect(); let mut b: Vec<(usize, i64)> = a.clone().into_iter().enumerate().collect(); b.sort_by_key(|b| b.1); let mut seg = vec![None; n + 1]; for i in 0..n { seg[i + 1] = update(seg[i].clone(), 0, n, b[i].0, b[i].1); } let mut sum = a.clone(); sum.push(0); for i in (0..n).rev() { sum[i] += sum[i + 1]; } for _ in 0..q { let l = it.next().unwrap().parse::().unwrap() - 1; let r = it.next().unwrap().parse::().unwrap(); let len = (r - l) as i64; let mut ng = 0; let mut ok = n; while ok - ng > 1 { let mid = (ok + ng) / 2; let (_, c) = find(&seg[mid], 0, n, l, r); if 2 * c >= len { ok = mid; } else { ng = mid; } } let (s, c) = find(&seg[ok], 0, n, l, r); let ans = (sum[l] - sum[r] - s - (len - c) * b[ok - 1].1) + (b[ok - 1].1 * c - s); writeln!(out, "{}", ans).ok(); // writeln!(out, "{} {} {}", s, c, b[ok - 1].1).ok(); } } fn main() { run(); }