#include #include #include #include #include #define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() const int INF = 0x3f3f3f3f; const long long LINF = 0x3f3f3f3f3f3f3f3fLL; const double EPS = 1e-8; const int MOD = 1000000007; // 998244353; const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1}; struct IOSetup { IOSetup() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(20); cerr << fixed << setprecision(10); } } iosetup; /*-------------------------------------------------*/ template struct BIT { BIT(int n, const Abelian &UNITY = 0) : n(n), UNITY(UNITY), dat(n, UNITY) {} void add(int idx, const Abelian &value) { while (idx < n) { dat[idx] += value; idx |= idx + 1; } } Abelian sum(int idx) { Abelian res = UNITY; while (idx >= 0) { res += dat[idx]; idx = (idx & (idx + 1)) - 1; } return res; } Abelian sum(int left, int right) { if (right < left) return UNITY; return sum(right) - sum(left - 1); } Abelian operator[](const int idx) { return sum(idx, idx); } int lower_bound(Abelian value) { if (value <= UNITY) return 0; int res = 0, exponent = 1; while (exponent <= n) exponent <<= 1; for (int mask = exponent >> 1; mask > 0; mask >>= 1) { if (res + mask - 1 < n && dat[res + mask - 1] < value) { value -= dat[res + mask - 1]; res += mask; } } return res; } private: int n; const Abelian UNITY; vector dat; }; struct Mo { Mo(const vector &left, const vector &right) : left(left), right(right) { n = left.size(); int width = sqrt(n); order.resize(n); iota(ALL(order), 0); sort(ALL(order), [&](int a, int b) { return left[a] / width != left[b] / width ? left[a] < left[b] : ((left[a] / width) & 1 ? right[a] < right[b] : right[a] > right[b]); }); } int process() { if (ptr == n) return -1; int idx = order[ptr]; while (left[idx] < nl) add(--nl); while (nr < right[idx]) add(nr++); while (nl < left[idx]) del(nl++); while (right[idx] < nr) del(--nr); ++ptr; return idx; } void add(int idx); void del(int idx); private: vector left, right, order; int n, ptr = 0, nl = 0, nr = 0; }; const int N = 200000; int b[N]; vector comp; BIT val(N); BIT cnt(N); void Mo::add(int idx) { val.add(b[idx], comp[b[idx]]); cnt.add(b[idx], 1); } void Mo::del(int idx) { val.add(b[idx], -comp[b[idx]]); cnt.add(b[idx], -1); } int main() { int n, q; cin >> n >> q; vector a(n); comp.resize(n); REP(i, n) { cin >> a[i]; comp[i] = a[i]; } sort(ALL(comp)); comp.erase(unique(ALL(comp)), comp.end()); REP(i, n) b[i] = lower_bound(ALL(comp), a[i]) - comp.begin(); vector ans(q, 0); vector left(q), right(q); REP(i, q) { int l, r; cin >> l >> r; --l; --r; left[i] = l; right[i] = r + 1; } Mo mo(left, right); REP(_, q) { int idx = mo.process(); if (idx == -1) assert(false); int kosu = (cnt.sum(N - 1) + 1) / 2; int mid = cnt.lower_bound(kosu); ans[idx] = -val.sum(mid - 1) + val.sum(mid, N - 1); ans[idx] += comp[mid] * cnt.sum(mid - 1) - comp[mid] * cnt.sum(mid, N); } REP(i, q) cout << ans[i] << '\n'; return 0; }