#include #include template class Compressor { private: std::vector cc; bool sorted; public: Compressor() : sorted(false) {} Compressor(const std::vector& a) { for (auto x : a) cc.push_back(x); build(); } void add(const T& x) { cc.push_back(x); sorted = false; } T operator[](int i) const { assert(sorted); return cc[i]; } int operator()(const T& x) const { assert(sorted); return lower_bound(begin(cc), end(cc), x) - begin(cc); } int size() const { assert(sorted); return cc.size(); } void build() { sort(begin(cc), end(cc)); cc.erase(unique(begin(cc), end(cc)), end(cc)); sorted = true; } static std::vector compressed(const std::vector& a) { Compressor c(a); std::vector res(a.size()); for(int i = 0; i < (int)a.size(); i++) res[i] = c(a[i]); return res; } }; template class FixedSet { struct S { T sum; int count; }; static S op(S a, S b) { return S{a.sum + b.sum, a.count + b.count}; } static S e() { return S{T{}, 0}; } using STree = atcoder::segtree; STree d; Compressor cc; size_t sz; int index(const T& x) { int p = cc(x); assert(0 <= p && p < cc.size() && cc[p] == x); return p; } public: FixedSet() {} FixedSet(const std::vector& A) { cc = Compressor(A); d = STree(cc.size()); sz = 0; } void add(const T& x, int c = 1) { int p = index(x); S pv = d.get(p); sz -= pv.count; int cnt = std::max(0, pv.count + c); d.set(p, S{x * cnt, cnt}); sz += cnt; } T top_k_sum(int k) { if (k == 0) return T{}; assert(k <= (int)size()); const auto f = [&](S x) { return x.count < k; }; int l = d.min_left(cc.size(), f) - 1; S res = d.prod(l, cc.size()); T sum = res.sum - cc[l] * (res.count - k); return sum; } T bottom_k_sum(int k) { if (k == 0) return T{}; assert(k <= (int)size()); const auto f = [&](S x) { return x.count < k; }; int r = d.max_right(0, f); S res = d.prod(0, r); T sum = res.sum + cc[r] * (k - res.count); return sum; } T kth_smallest(int k) { assert(0 < k && k <= sz); const auto f = [&](S x) { return x.count < k; }; int r = d.max_right(0, f); return cc[r]; } T kth_largest(int k) { return kth_smallest(sz - k + 1); } size_t size() const { return sz; } bool empty() const { return size() == 0; } int count(const T& x) { int pos = index(x); return d.get(pos).count; } T sum() const { return d.all_prod().sum; } }; using namespace std; int N, Q; const int maxn = 2 << 17; int A[maxn], L[maxn], R[maxn]; long long S[maxn]; int ord[maxn]; long long ans[maxn]; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); cin >> N >> Q; for (int i = 0; i < N; i++) { cin >> A[i]; S[i + 1] = S[i] + A[i]; } const int B = std::max(1, 1.0 * N / std::max(1.0, std::sqrt(Q) * 2.0 / 3.0)); for (int i = 0; i < Q; i++) { ord[i] = i; cin >> L[i] >> R[i]; L[i]--; } sort(ord, ord + Q, [&](int i, int j) -> bool { int iblock = L[i] / B, jblock = L[j] / B; if (iblock != jblock) return iblock < jblock; if (iblock & 1) return R[i] < R[j]; return R[i] > R[j]; }); FixedSet st(vector{A, A + N}); int nl = 0, nr = 0; for (int qi = 0; qi < Q; qi++) { int i = ord[qi]; while (nl > L[i]) st.add(A[--nl]); while (nr < R[i]) st.add(A[nr++]); while (nl < L[i]) st.add(A[nl++], -1); while (nr > R[i]) st.add(A[--nr], -1); int W = R[i] - L[i]; int m = (W + 1) / 2; long long mid = st.kth_largest(m); long long top = st.top_k_sum(W - m); long long bot = (S[R[i]] - S[L[i]] - top); ans[i] = top - mid * (W - m) + mid * m - bot; } for (int i = 0; i < Q; i++) cout << ans[i] << "\n"; }