// need #include #include // data structure #include #include #include #include #include #include #include #include #include //#include #include #include #include #include // etc #include #include #include #include #include #include #include #include // input #define INIT std::ios::sync_with_stdio(false);std::cin.tie(0); #define VAR(type, ...)type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__); template void MACRO_VAR_Scan(T& t) { std::cin >> t; } templatevoid MACRO_VAR_Scan(First& first, Rest& ...rest) { std::cin >> first; MACRO_VAR_Scan(rest...); } #define VEC_ROW(type, n, ...)std::vector __VA_ARGS__;MACRO_VEC_ROW_Init(n, __VA_ARGS__); for(int w_=0; w_ void MACRO_VEC_ROW_Init(int n, T& t) { t.resize(n); } templatevoid MACRO_VEC_ROW_Init(int n, First& first, Rest& ...rest) { first.resize(n); MACRO_VEC_ROW_Init(n, rest...); } template void MACRO_VEC_ROW_Scan(int p, T& t) { std::cin >> t[p]; } templatevoid MACRO_VEC_ROW_Scan(int p, First& first, Rest& ...rest) { std::cin >> first[p]; MACRO_VEC_ROW_Scan(p, rest...); } #define VEC(type, c, n) std::vector c(n);for(auto& i:c)std::cin>>i; #define MAT(type, c, m, n) std::vector> c(m, std::vector(n));for(auto& R:c)for(auto& w:R)std::cin>>w; // output templatevoid MACRO_OUT(const T t) { std::cout << t; } templatevoid MACRO_OUT(const First first, const Rest...rest) { std::cout << first << " "; MACRO_OUT(rest...); } #define OUT(...) MACRO_OUT(__VA_ARGS__); #define FOUT(n, dist) std::cout<=(a);--w) #define REP(w, n) for(int w=0;w=0;--w) #define IN(a, x, b) (a<=x && x inline T CHMAX(T & a, const T b) { return a = (a < b) ? b : a; } template inline T CHMIN(T& a, const T b) { return a = (a > b) ? b : a; } // test template using V = std::vector; template using VV = V>; template std::ostream& operator<<(std::ostream& os, std::pair p) { os << "(" << p.first << ", " << p.second << ")"; return os; } // type/const #define int ll using ll = long long; using ull = unsigned long long; using ld = long double; using PAIR = std::pair; using PAIRLL = std::pair; constexpr int INFINT = (1 << 30) - 1; // 1.07x10^ 9 constexpr int INFINT_LIM = (1LL << 31) - 1; // 2.15x10^ 9 constexpr ll INFLL = 1LL << 60; // 1.15x10^18 constexpr ll INFLL_LIM = (1LL << 62) - 1 + (1LL << 62); // 9.22x10^18 constexpr double EPS = 1e-10; constexpr int MOD = 998244353; constexpr double PI = 3.141592653589793238462643383279; template void FILL(T(&a)[N], const T & val) { for (auto& x : a) x = val; } template void FILL(ARY(&a)[N][M], const T & val) { for (auto& b : a) FILL(b, val); } template void FILL(std::vector & a, const T & val) { for (auto& x : a) x = val; } template void FILL(std::vector> & a, const T & val) { for (auto& b : a) FILL(b, val); } // ------------>8------------------------------------->8------------ class Mo { std::vector Ls, Rs, o; std::vector v; int width; int nl, nr, ptr; inline void distribute(int idx) { v[idx].flip(); if (v[idx]) add(idx); else del(idx); } void add(int i); void del(int i); public: Mo(int n) : width((int)std::sqrt(n)), nl(0), nr(0), ptr(0), v(n) {} // [l, r)に対するクエリを追加 void insert(int l, int r) { Ls.emplace_back(l); Rs.emplace_back(r); } // クエリをソート void build() { o.resize(Ls.size()); std::iota(o.begin(), o.end(), 0); std::sort(o.begin(), o.end(), [&](int a, int b) { if (Ls[a] / width != Ls[b] / width) return Ls[a] < Ls[b]; return Rs[a] < Rs[b]; }); } // クエリを1つ分進めてクエリのidを返す int process() { if (ptr == o.size()) return -1; const auto id = o[ptr]; while (nl > Ls[id]) distribute(--nl); while (nr < Rs[id]) distribute(nr++); while (nl < Ls[id]) distribute(nl++); while (nr > Rs[id]) distribute(--nr); return o[ptr++]; } }; struct BIT { int N; using TYPE = int; std::vector bit; BIT() : N(0) {} BIT(int n) : N(n), bit(N + 1, 0) {} BIT(int n, TYPE init) : N(n), bit(N + 1, init) {} // bit[i] += w; void add(int i, TYPE w) { for (int x = ++i; x <= N; x += x & -x) bit[x] += w; } // return sum [0, i); TYPE sum(int i) { TYPE res = 0; for (int x = i; x > 0; x -= x & -x) res += bit[x]; return res; } // return sum [i, j); TYPE sum(int i, int j) { return sum(j) - sum(i); } const TYPE& operator[](const int& i) const { return bit[i]; } }; int sz; V a; V inv; BIT bit1, bit2; int cnt = 0; int val = 0; void Mo::add(int i) { ++cnt; bit1.add(a[i], 1); bit2.add(a[i], inv[a[i]]); } void Mo::del(int i) { --cnt; bit1.add(a[i], -1); bit2.add(a[i], -inv[a[i]]); } signed main() { INIT; VAR(int, n, Q); VEC(int, a_, n); a = a_; VEC_ROW(int, Q, l, r); { std::map map; REP(i, n) map[a[i]]; for (auto& p : map) { p.second = sz; inv.emplace_back(p.first); ++sz; } REP(i, n) a[i] = map[a[i]]; } bit1 = BIT(sz); bit2 = BIT(sz); V ans(Q); Mo mo(n); REP(i, Q) mo.insert(--l[i], r[i]); mo.build(); REP(i, Q) { int idx = mo.process(); int l = 0, r = sz; while (r - l > 1) { int me = (l + r) / 2; if (bit1.sum(me) >= (cnt + 1) / 2) r = me; else l = me; } val = 0; int cnt1 = bit1.sum(l); val += inv[l] * cnt1 - bit2.sum(l); val += bit2.sum(l, sz) - inv[l] * (cnt - cnt1); ans[idx] = val; } REP(i, Q) { OUT(ans[i])BR; } return 0; }