//#pragma warning(disable:4996) //#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include #include #include #include #include //#include //< in.txt > out.txt using namespace std; //std::ios::sync_with_stdio(false); //std::cin.tie(0); const long long MOD = 1e9 + 7; const long long INF = 1e18; typedef long long LL; typedef long double LD; typedef unsigned long long ULL; //typedef boost::multiprecision::cpp_int bigint; typedef pair PLL; typedef pair PI; typedef pair pdl; typedef pair pdd; typedef vector VLL; typedef vector VVLL; typedef vector VI; typedef vector> VVI; typedef unsigned long long ULL; template using pqueue = priority_queue, function>; template inline void chmin(T& a, T b) { a = min(a, b); } template inline void chmax(T& a, T b) { a = max(a, b); } //y/xのfloorを求める LL floor_(LL y, LL x) { if (x < 0) { x *= -1; y *= -1; } if (y >= 0) { return y / x; } else { if ((-y) % x == 0) { return y / x; } else { return -((-y) / x) - 1; } } } inline LL mod(LL a, LL m) { LL res = a % m; return res >= 0 ? res : res + m; } void input(); void solve(); void daminput(); void naive(); void outputinput(); int main() { std::cin.tie(0); std::ios::sync_with_stdio(false); cout << fixed << setprecision(12); input(); //daminput(); solve(); //naive(); //outputinput(); return 0; } ////////////////////////////////////////////////// ////////////////////////////////////////////////// template class CPSegmentTree { public: CPSegmentTree() {} void build(int n, function tt, T t0) { TT = tt; T0 = t0; height = 1; //2の累乗化 int rn = 1; while (rn < n) { rn *= 2; height++; } N = rn; ar.resize(2 * N - 1, t0); cl.resize(2 * N - 1, -1); cr.resize(2 * N - 1, -1); time.resize(2 * N - 1, 0); for (int n = 0; n < N - 1; n++) { cl[n] = 2 * n + 1; cr[n] = 2 * n + 2; } roots.push_back(0); } void build(vector& ar0, function tt, T t0) { TT = tt; T0 = t0; N = ar0.size(); int rn = 1; while (rn < N) { rn *= 2; height++; } N = rn; cl.resize(2 * N - 1, -1); cr.resize(2 * N - 1, -1); time.resize(2 * N - 1, 0); for (int n = 0; n < N - 1; n++) { cl[n] = 2 * n + 1; cr[n] = 2 * n + 2; } ar.resize(2 * N - 1, t0); for (int n = 0; n < ar0.size(); n++) { ar[N - 1 + n] = ar0[n]; } for (int n = N - 2; n >= 0; n--) { ar[n] = TT(ar[cl[n]], ar[cr[n]]); } roots.push_back(0); } //時間tの木のコピーを作る この木を表す時間を返す //(コピー元の木をこの後いじると壊れる) int copy(int t) { int oldr = roots[t]; int newt = roots.size(); roots.push_back(ar.size()); ar.push_back(ar[oldr]); cl.push_back(cl[oldr]); cr.push_back(cr[oldr]); time.push_back(newt); return newt; } //時間tの頂点nをxに更新 void set(int t, int n, T x) { set_node(t, roots[t], 0, N, n, x); } //時刻tにおける、[l,r)の範囲の積を返す T get(int t, int l, int r) { return get_node(l, r, roots[t], 0, N); } //時間tにおける、葉nの値 T get(int t, int n) { return get(t, n, n + 1); } private: //要素数(2の累乗化済み) int N; //要素 vector ar; //左右の子は何か VI cl, cr; //積 function TT; //単位元 T T0; //時刻tにおける根のid(はじめの時刻は0) VI roots; //この木の高さ int height; //各頂点の属する時間 VI time; //時間tの頂点pに対する更新処理 //範囲[l,r)を持つ //更新処理をした結果の自分の頂点番号を返す(新しく時間tに頂点を登録した場合) int set_node(int t, int p, int l, int r, int n, T x) { //頂点pが時間tの頂点でなければ、新しい頂点を作ったうえで変更 if (time[p] != t) { int newp = ar.size(); ar.push_back(ar[p]); cl.push_back(cl[p]); cr.push_back(cr[p]); time.push_back(t); p = newp; } //この頂点が頂点n自身の場合 if (l == n && r == n + 1) { ar[p] = x; return p; } //左の子は[l,m)、右の子は[m,r)を持つ int m = (r - l) / 2 + l; //頂点nが左の子に含まれる場合 if (n < m) { cl[p] = set_node(t, cl[p], l, m, n, x); } //頂点nが右の子に含まれる場合 else { cr[p] = set_node(t, cr[p], m, r, n, x); } ar[p] = TT(ar[cl[p]], ar[cr[p]]); return p; } //再帰用 n:=見る頂点、頂点nの表す範囲は[s,e) T get_node(int l, int r, int n, int s, int e) { if (l <= s && e <= r) { return ar[n]; } //左の子は[s,m)、右の子は[m,e)を持つ int m = (e - s) / 2 + s; T res = T0; //左の子が[l,r)とかぶる if (r > s && m > l) { res = get_node(l, r, cl[n], s, m); } //右の子が[l,r)とかぶる if (r > m && e > l) { res = TT(res, get_node(l, r, cr[n], m, e)); } return res; } }; //座圧 class CoordComp { public: int N; VI new2old; map old2new; CoordComp() :N(0) {}; //vに含まれる数に昇順で添え字(0-index)を設定する(vは変更しない) void build(VLL& v) { set all; for (LL t : v) { all.insert(t); } N = all.size(); new2old.reserve(N); int i = 0; for (LL t : all) { old2new.insert(pair(t, i++)); new2old.push_back(t); } } //tを圧縮した座標を返す LL conv(int t) { return old2new[t]; } //[l,r)が含む登録点の集合を変換後の座標の区間[s,e)で返す(登録点が存在しなければ[-1,-1)を返す) PI conv(LL l, LL r) { //new2old[s1] < l <= new2old[s2] int s1 = -1, s2 = N; while (s2 - s1 > 1) { int m = (s1 + s2) / 2; if (new2old[m] < l) { s1 = m; } else { s2 = m; } } //new2old[e1] < r <= new2old[e2] int e1 = -1, e2 = N; while (e2 - e1 > 1) { int m = (e2 + e1) / 2; if (new2old[m] < r) { e1 = m; } else { e2 = m; } } if (s2 >= e2) { return PI(-1, -1); } return PI(s2, e2); } //圧縮済みの座標から、元の数を返す LL revconv(int i) { return new2old[i]; } //登録点の個数 int size() { return N; } }; int N, Q; VLL A; void input() { cin >> N >> Q; A.resize(N); for (int n = 0; n < N; n++) { cin >> A[n]; } } void daminput() { } void solve() { CoordComp coord; coord.build(A); CPSegmentTree seg_count; seg_count.build(coord.size(), [](int a, int b) { return a + b; }, 0); CPSegmentTree seg_sum; seg_sum.build(coord.size(), [](LL a, LL b) { return a + b; }, 0); for (int n = 0; n < N; n++) { int conv = coord.conv(A[n]); int old_c = seg_count.get(n, conv); seg_count.set(n, conv, old_c + 1); LL old_s = seg_sum.get(n, conv); seg_sum.set(n, conv, old_s + A[n]); seg_count.copy(n); seg_sum.copy(n); } for (int query = 0; query < Q; query++) { int l, r; cin >> l >> r; l--; r--; //count[t=l~r][0,s] < (r-l)/2 + 1 <= count[t=l~r][0,e] -> e int s = -1, e = coord.size(); while (e - s > 1) { int m = (e + s) / 2; int c = seg_count.get(r, 0, m + 1); if (l - 1 >= 0) { c -= seg_count.get(l - 1, 0, m + 1); } if (c < (r - l) / 2 + 1) { s = m; } else { e = m; } } int p = seg_count.get(r, 0, e + 1); if (l - 1 >= 0) { p -= seg_count.get(l - 1, 0, e + 1); } int q = (r-l+1) - p; LL x = coord.revconv(e); LL ans = x * p; ans -= seg_sum.get(r, 0, e + 1); if (l - 1 >= 0) { ans += seg_sum.get(l - 1, 0, e + 1); } ans -= x * q; ans += seg_sum.get(r, e + 1, coord.size()); if (l - 1 >= 0) { ans -= seg_sum.get(l - 1, e + 1, coord.size()); } cout << ans << "\n"; } } void naive() { } void outputinput() { }