#line 2 "template.hpp" // #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include using namespace std; template concept Streamable = requires(ostream os, T &x) { os << x; }; template concept is_modint = requires(mint &x) { { x.val() } -> std::convertible_to; }; #ifdef LOCAL #include #else #define debug(...) #endif template void print_one(const T &value) { cout << value; } template void print_one(const T &value) { cout << value.val(); } void print() { cout << '\n'; } template void print(const T &a, const Ts &...b) { print_one(a); ((cout << ' ', print_one(b)), ...); cout << '\n'; } template requires(!Streamable) void print(const Iterable &v) { for(auto it = v.begin(); it != v.end(); ++it) { if(it != v.begin()) cout << " "; print_one(*it); } cout << '\n'; } using ll = long long; using vl = vector; using vll = vector; using P = pair; #define all(v) v.begin(), v.end() template inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); } template inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); } // https://trap.jp/post/1224/ template constexpr auto min(T... a) { return min(initializer_list>{a...}); } template constexpr auto max(T... a) { return max(initializer_list>{a...}); } template void input(T &...a) { (cin >> ... >> a); } template void input(vector &a) { for(T &x : a) cin >> x; } #define INT(...) \ int __VA_ARGS__; \ input(__VA_ARGS__) #define LL(...) \ long long __VA_ARGS__; \ input(__VA_ARGS__) #define STR(...) \ string __VA_ARGS__; \ input(__VA_ARGS__) #define REP1(a) for(ll i = 0; i < a; i++) #define REP2(i, a) for(ll i = 0; i < a; i++) #define REP3(i, a, b) for(ll i = a; i < b; i++) #define REP4(i, a, b, c) for(ll i = a; i < b; i += c) #define overload4(a, b, c, d, e, ...) e #define rep(...) overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__) #define rep1(i, n) for(ll i = 1; i <= ((ll)n); ++i) ll inf = 3e18; vl dx = {1, -1, 0, 0}; vl dy = {0, 0, 1, -1}; #line 3 "data_structure/persistent-segtree.hpp" // https://ei1333.github.io/library/structure/segment-tree/persistent-segment-tree.hpp.html // https://37zigen.com/persistent-segment-tree/ template struct persistent_segtree { private: int n; struct Node { S s; Node *l, *r; }; vector> pool; Node *make_node_ptr(Node node) { pool.emplace_back(make_unique(node)); return pool.back().get(); } // 区間[l,r)がノードに対応する // [0,v.size())が根 Node *build(int l, int r, const vector &v) { if(l + 1 == r) { return make_node_ptr(Node(v[l])); } int m = (l + r) >> 1; Node *lp = build(l, m, v), *rp = build(m, r, v); return make_node_ptr(Node(op(lp->s, rp->s), lp, rp)); } // [a,b) 積を取る区間 // [l,r) pが対応する区間 S prod(int a, int b, Node *p, int l, int r) { if(r <= a or b <= l) return e(); if(a <= l and r <= b) return p->s; int m = (l + r) >> 1; return op(prod(a, b, p->l, l, m), prod(a, b, p->r, m, r)); } Node *merge(Node *lp, Node *rp) { return make_node_ptr(Node(op(lp->s, rp->s), lp, rp)); } Node *set(int k, const S &s, Node *p, int l, int r) { assert(p); if(k < l or r <= k) return p; if(l == k and k + 1 == r) { return make_node_ptr(Node(s)); } int m = (l + r) >> 1; Node *lp = set(k, s, p->l, l, m), *rp = set(k, s, p->r, m, r); return merge(lp, rp); } public: using node_type = Node; persistent_segtree(int n) : n(n) {} Node *build(const vector &v) { return build(0, v.size(), v); } // [a,b) の総積を計算 S prod(Node *p, int a, int b) { return prod(a, b, p, 0, n); } Node *set(Node *p, int k, const S &s) { return set(k, s, p, 0, n); } void dump(Node *p, vector &res) { assert((p->l == nullptr) == (p->r == nullptr)); if(p->l) { dump(p->l, res); dump(p->r, res); } else { res.emplace_back(p->s); } } }; #line 3 "/home/y_midori/cp/a.cpp" P operator-(const P &p, const P &q) { return P(p.first - q.first, p.second - q.second); } void solve() { INT(n, q); vl a(n); input(a); vector ord(n), rev(n); iota(all(ord), 0); ranges::sort(ord, {}, [&a](int i) { return a[i]; }); for(int i = 0; i < n; i++) rev[ord[i]] = i; persistent_segtree< P, [](P x, P y) { return P(x.first + y.first, x.second + y.second); }, [] { return P(0, 0); }> seg(n); using pointer = decltype(seg)::node_type *; vector v{seg.build(vector

(n))}; for(int i = 0; i < n; i++) { v.emplace_back(seg.set(v.back(), rev[i], P(a[i], 1))); } ranges::sort(a); auto cul = [&](int l, int r) -> ll { int ok = 0, ng = n; while(ng > ok + 1) { int mid = (ok + ng) >> 1; if(seg.prod(v[r], 0, mid).second - seg.prod(v[l], 0, mid).second <= (r - l) / 2) { ok = mid; } else ng = mid; } P small = seg.prod(v[r], 0, ok) - seg.prod(v[l], 0, ok); P large = seg.prod(v[r], ok, n) - seg.prod(v[l], ok, n); ll ans = large.first - small.first + a[ok] * (small.second - large.second); return ans; }; while(q--) { INT(l, r); --l; print(cul(l, r)); } } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); solve(); }