// #define _GLIBCXX_DEBUG #include // clang-format off std::ostream&operator<<(std::ostream&os,std::int8_t x){return os<<(int)x;} std::ostream&operator<<(std::ostream&os,std::uint8_t x){return os<<(int)x;} std::ostream&operator<<(std::ostream&os,const __int128_t &v){if(!v)os<<"0";__int128_t tmp=v<0?(os<<"-",-v):v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os< #define MEMBER_MACRO(member, Dummy, name, type1, type2, last) \ template struct name##member { \ template static type1 check(U *); \ static type2 check(...); \ static tClass *mClass; \ last; \ } #define HAS_CHECK(member, Dummy) MEMBER_MACRO(member, Dummy, has_, std::true_type, std::false_type, static const bool value= decltype(check(mClass))::value) #define HAS_MEMBER(member) HAS_CHECK(member, int dummy= (&U::member, 0)) #define HAS_TYPE(member) HAS_CHECK(member, class dummy= typename U::member) #define HOGE_OR(member, name, type2) \ MEMBER_MACRO(member, class dummy= typename U::member, name, typename U::member, type2, using type= decltype(check(mClass))); \ template using name##member##_t= typename name##member::type #define NULLPTR_OR(member) HOGE_OR(member, nullptr_or_, std::nullptr_t) #define MYSELF_OR(member) HOGE_OR(member, myself_or_, tClass) template static constexpr bool tuple_like_v= false; template static constexpr bool tuple_like_v> = true; template static constexpr bool tuple_like_v> = true; template static constexpr bool tuple_like_v> = true; template auto to_tuple(const T &t) { if constexpr (tuple_like_v) return std::apply([](auto &&...x) { return std::make_tuple(x...); }, t); } template auto forward_tuple(const T &t) { if constexpr (tuple_like_v) return std::apply([](auto &&...x) { return std::forward_as_tuple(x...); }, t); } template static constexpr bool array_like_v= false; template static constexpr bool array_like_v> = true; template static constexpr bool array_like_v> = std::is_convertible_v; template static constexpr bool array_like_v> = true; template static constexpr bool array_like_v> = array_like_v> && std::is_convertible_v; template auto to_array(const T &t) { if constexpr (array_like_v) return std::apply([](auto &&...x) { return std::array{x...}; }, t); } template using to_tuple_t= decltype(to_tuple(T())); template using to_array_t= decltype(to_array(T())); // clang-format off templatestruct make_long{using type= T;}; template<>struct make_long{using type= int16_t;}; template<>struct make_long{using type= uint16_t;}; template<>struct make_long{using type= int32_t;}; template<>struct make_long{using type= uint32_t;}; template<>struct make_long{using type= int64_t;}; template<>struct make_long{using type= uint64_t;}; template<>struct make_long{using type= __int128_t;}; template<>struct make_long{using type= __uint128_t;}; template<>struct make_long{using type= double;}; template<>struct make_long{using type= long double;}; template using make_long_t= typename make_long::type; // clang-format on namespace kdtree_internal { template class KDTreeImpl {}; template class KDTreeImpl, std::tuple> { HAS_MEMBER(op); HAS_MEMBER(ti); HAS_MEMBER(mp); HAS_MEMBER(cp); HAS_TYPE(T); HAS_TYPE(E); MYSELF_OR(T); NULLPTR_OR(E); using Sec= std::array; using Pos= std::array; using Range= std::array; using long_pos_t= make_long_t; template static constexpr bool monoid_v= std::conjunction_v, has_op, has_ti>; template static constexpr bool dual_v= std::conjunction_v, has_E, has_mp, has_cp>; struct Node_BB { int ch[2]= {-1, -1}; Pos pos; pos_t range[K][2]; }; template struct Node_B: Node_BB { U val; }; template struct Node_D: Node_B {}; template struct Node_D: Node_BB {}; template struct Node_D: Node_B { typename M::T sum; }; template struct Node_D: Node_B { typename M::E laz; bool laz_flg= false; }; template struct Node_D: Node_B { typename M::T sum; typename M::E laz; bool laz_flg= false; }; using Node= Node_D, dual_v>; using Iter= typename std::vector::iterator; using T= std::conditional_t, std::nullptr_t, myself_or_T_t>; using E= nullptr_or_E_t; template using canbe_Pos= std::is_convertible, std::tuple>; template using canbe_PosV= std::is_convertible, std::tuple>; template static constexpr bool canbe_Pos_and_T_v= std::conjunction_v, std::is_convertible>; std::vector ns; static inline T def_val() { if constexpr (monoid_v) return M::ti(); else return T(); } template static inline auto get_(const P &p) { if constexpr (z) return std::get(p); else return std::get(p.first); } template Range to_range(const P &p, std::index_sequence) { return {(assert(std::get(p) <= std::get(p)), Sec{std::get(p), std::get(p)})...}; } inline void update(int t) { ns[t].sum= ns[t].val; if (ns[t].ch[0] != -1) ns[t].sum= M::op(ns[t].sum, ns[ns[t].ch[0]].sum); if (ns[t].ch[1] != -1) ns[t].sum= M::op(ns[t].sum, ns[ns[t].ch[1]].sum); } inline void propagate(int t, const E &x) { if (t == -1) return; if (ns[t].laz_flg) M::cp(ns[t].laz, x); else ns[t].laz= x, ns[t].laz_flg= true; M::mp(ns[t].val, x); if constexpr (monoid_v) M::mp(ns[t].sum, x); } inline void push(int t) { if (ns[t].laz_flg) ns[t].laz_flg= false, propagate(ns[t].ch[0], ns[t].laz), propagate(ns[t].ch[1], ns[t].laz); } template inline void set_range(int t, int m, Iter bg, Iter ed, const P *p) { auto [mn, mx]= std::minmax_element(bg, ed, [&](int a, int b) { return get_(p[a]) < get_(p[b]); }); ns[t].range[k][0]= get_(p[*mn]), ns[t].range[k][1]= get_(p[*mx]), ns[t].pos[k]= get_(p[m]); } template inline void set_range_lp(int t, int m, Iter bg, Iter ed, const P *p, std::index_sequence) { (void)(int[]){(set_range(t, m, bg, ed, p), 0)...}; } template inline int build(int &ts, Iter bg, Iter ed, const P *p, const T &v= def_val()) { if (bg == ed) return -1; auto md= bg + (ed - bg) / 2; int t= ts++; std::nth_element(bg, md, ed, [&](int a, int b) { return get_(p[a]) < get_(p[b]); }), set_range_lp(t, *md, bg, ed, p, std::make_index_sequence()); if constexpr (z) { if constexpr (!std::is_void_v) { if constexpr (std::tuple_size_v

== K + 1) ns[t].val= std::get(p[*md]); else ns[t].val= v; } } else ns[t].val= p[*md].second; static constexpr uint8_t nx= div + 1 == K ? 0 : div + 1; ns[t].ch[0]= build(ts, bg, md, p, v), ns[t].ch[1]= build(ts, md + 1, ed, p, v); if constexpr (monoid_v) update(t); return t; } template inline int build(Iter bg, Iter ed, const P *p, int &ts) { if (bg == ed) return -1; auto md= bg + (ed - bg) / 2; int t= ts++; std::nth_element(bg, md, ed, [&](int a, int b) { return get_(p[a]) < get_(p[b]); }), set_range_lp(t, bg, ed, p, std::make_index_sequence()); if constexpr (z) { if constexpr (!std::is_void_v) { if constexpr (std::tuple_size_v

== K + 1) ns[t].val= std::get(p[t]); else ns[t].val= def_val(); } } else ns[t].val= p[t].second; static constexpr uint8_t nx= div + 1 == K ? 0 : div + 1; ns[t].ch[0]= build(bg, md, p, ts), ns[t].ch[1]= build(md + 1, ed, p, ts); if constexpr (monoid_v) update(t); return t; } static inline auto in_cuboid(const Range &r) { return [r](const Pos &pos) { for (uint8_t k= K; k--;) if (r[k][1] < pos[k] || pos[k] < r[k][0]) return false; return true; }; } static inline auto out_cuboid(const Range &r) { return [r](const pos_t rr[K][2]) { for (uint8_t k= K; k--;) if (rr[k][1] < r[k][0] || r[k][1] < rr[k][0]) return true; return false; }; } static inline auto inall_cuboid(const Range &r) { return [r](const pos_t rr[K][2]) { for (uint8_t k= K; k--;) if (rr[k][0] < r[k][0] || r[k][1] < rr[k][1]) return false; return true; }; } static inline long_pos_t min_dist2(const pos_t r[K][2], const Pos &pos) { long_pos_t d2= 0, dx; for (uint8_t k= K; k--;) dx= std::clamp(pos[k], r[k][0], r[k][1]) - pos[k], d2+= dx * dx; return d2; } static inline auto in_ball(const Pos &c, long_pos_t r2) { return [c, r2](const Pos &pos) { long_pos_t d2= 0, dx; for (uint8_t k= K; k--;) dx= pos[k] - c[k], d2+= dx * dx; return d2 <= r2; }; } static inline auto inall_ball(const Pos &c, long_pos_t r2) { return [c, r2](const pos_t rr[K][2]) { long_pos_t d2= 0, dx0, dx1; for (uint8_t k= K; k--;) dx0= rr[k][0] - c[k], dx1= rr[k][1] - c[k], d2+= std::max(dx0 * dx0, dx1 * dx1); return d2 <= r2; }; } static inline auto out_ball(const Pos &c, long_pos_t r2) { return [c, r2](const pos_t r[K][2]) { return min_dist2(r, c) > r2; }; } inline void nns(int t, const Pos &pos, std::pair &ret) const { if (t == -1) return; long_pos_t d2= min_dist2(ns[t].range, pos); if (ret.first != -1 && d2 >= ret.second) return; long_pos_t dx= d2= 0; for (uint8_t k= K; k--;) dx= pos[k] - ns[t].pos[k], d2+= dx * dx; if (ret.first == -1 || d2 < ret.second) ret= {t, d2}; bool f= 0; if (auto [l, r]= ns[t].ch; l != -1 && r != -1) f= min_dist2(ns[l].range, pos) > min_dist2(ns[r].range, pos); nns(ns[t].ch[f], pos, ret), nns(ns[t].ch[!f], pos, ret); } template inline void col(int t, const In &in, const Out &out, std::vector &ret) const { if (t == -1 || out(ns[t].range)) return; if (in(ns[t].pos)) ret.push_back(ns[t].val); col(ns[t].ch[0], in, out, ret), col(ns[t].ch[1], in, out, ret); } template inline T fld(int t, const In &in, const InAll &inall, const Out &out) { if (t == -1 || out(ns[t].range)) return def_val(); if (inall(ns[t].range)) return ns[t].sum; if constexpr (dual_v) push(t); T ret= M::op(fld(ns[t].ch[0], in, inall, out), fld(ns[t].ch[1], in, inall, out)); return in(ns[t].pos) ? M::op(ret, ns[t].val) : ret; } template inline void app(int t, const In &in, const InAll &inall, const Out &out, const E &x) { if (t == -1 || out(ns[t].range)) return; if (inall(ns[t].range)) return propagate(t, x); if (push(t); in(ns[t].pos)) M::mp(ns[t].val, x); app(ns[t].ch[0], in, inall, out, x), app(ns[t].ch[1], in, inall, out, x); if constexpr (monoid_v) update(t); } template inline bool set(int t, const Pos &pos, const T &x) { if (t == -1) return false; bool isok= true; for (uint8_t k= K; k--; isok&= pos[k] == ns[t].pos[k]) if (ns[t].range[k][1] < pos[k] || pos[k] < ns[t].range[k][0]) return false; if constexpr (dual_v) push(t); if (isok) { if constexpr (z) ns[t].val= x; else ns[t].val= M::op(ns[t].val, x); } else if (!(isok= set(ns[t].ch[0], pos, x))) isok= set(ns[t].ch[1], pos, x); if constexpr (monoid_v) if (isok) update(t); return isok; } inline std::pair get(int t, const Pos &pos) { if (t == -1) return {T(), false}; bool myself= true; for (uint8_t k= K; k--; myself&= pos[k] == ns[t].pos[k]) if (ns[t].range[k][1] < pos[k] || pos[k] < ns[t].range[k][0]) return {T(), false}; if (myself) return {ns[t].val, true}; if constexpr (dual_v) push(t); auto ret= get(ns[t].ch[0], pos); return !ret.second ? get(ns[t].ch[1], pos) : ret; } public: template , canbe_PosV

>>> KDTreeImpl(const P *p, size_t n): ns(n) { std::vector ids(n); int ts= 0; std::iota(ids.begin(), ids.end(), 0), build<1, 0>(ts, ids.begin(), ids.end(), p); } template , canbe_PosV

>>> KDTreeImpl(const std::vector

&p): KDTreeImpl(p.data(), p.size()) {} template ::value>> KDTreeImpl(const std::set

&p): KDTreeImpl(std::vector(p.begin(), p.end())) {} template >> KDTreeImpl(const P *p, size_t n, U v): ns(n) { std::vector ids(n); int ts= 0; std::iota(ids.begin(), ids.end(), 0), build<1, 0>(ts, ids.begin(), ids.end(), p, v); } template >> KDTreeImpl(const std::vector

&p, U v): KDTreeImpl(p.data(), p.size(), v) {} template >> KDTreeImpl(const std::set

&p, U v): KDTreeImpl(std::vector(p.begin(), p.end()), v) {} template >> KDTreeImpl(const std::pair *p, size_t n): ns(n) { std::vector ids(n); int ts= 0; std::iota(ids.begin(), ids.end(), 0), build<0, 0>(ts, ids.begin(), ids.end(), p); } template >> KDTreeImpl(const std::vector> &p): KDTreeImpl(p.data(), p.size()) {} template >> KDTreeImpl(const std::map &p): KDTreeImpl(std::vector(p.begin(), p.end())) {} std::vector enum_cuboid(PK2... xs) { static_assert(!std::is_void_v, "\"enum_cuboid\" is not available"); std::vector ret; auto r= to_range(std::forward_as_tuple(xs...), std::make_index_sequence()); return col(-ns.empty(), in_cuboid(r), out_cuboid(r), ret), ret; } std::vector enum_ball(PK... xs, pos_t r) const { static_assert(!std::is_void_v, "\"enum_ball\" is not available"); std::vector ret; long_pos_t r2= long_pos_t(r) * r; return col(-ns.empty(), in_ball({xs...}, r2), out_ball({xs...}, r2), ret), ret; } T fold_cuboid(PK2... xs) { static_assert(monoid_v, "\"fold_cuboid\" is not available"); auto r= to_range(std::forward_as_tuple(xs...), std::make_index_sequence()); return fld(-ns.empty(), in_cuboid(r), inall_cuboid(r), out_cuboid(r)); } T fold_ball(PK... xs, pos_t r) { static_assert(monoid_v, "\"fold_ball\" is not available"); long_pos_t r2= long_pos_t(r) * r; return fld(-ns.empty(), in_ball({xs...}, r2), inall_ball({xs...}, r2), out_ball({xs...}, r2)); } void apply_cuboid(PK2... xs, E a) { static_assert(dual_v, "\"apply_cuboid\" is not available"); auto r= to_range(std::forward_as_tuple(xs...), std::make_index_sequence()); app(-ns.empty(), in_cuboid(r), inall_cuboid(r), out_cuboid(r), a); } void apply_ball(PK... xs, pos_t r, E a) { static_assert(dual_v, "\"apply_ball\" is not available"); long_pos_t r2= long_pos_t(r) * r; app(-ns.empty(), in_ball({xs...}, r2), inall_ball({xs...}, r2), out({xs...}, r2), a); } void set(PK... xs, T v) { assert(ns.size()), assert(set<1>(0, {xs...}, v)); } void mul(PK... xs, T v) { static_assert(monoid_v, "\"mul\" is not available"); assert(ns.size()), assert(set<0>(0, {xs...}, v)); } T get(PK... xs) { assert(ns.size()); auto [ret, flg]= get(0, {xs...}); return assert(flg), ret; } Pos nearest_neighbor(PK... xs) const { assert(ns.size()); std::pair ret= {-1, -1}; return nns(0, {xs...}, ret), ns[ret.first].pos; } }; template using KDTree= KDTreeImpl>, to_tuple_t>>; } using kdtree_internal::KDTree; template class WaveletMatrix { struct SuccinctIndexableDictionary { std::size_t len, blocks, zeros; std::vector bit, sum; SuccinctIndexableDictionary()= default; SuccinctIndexableDictionary(std::size_t len): len(len), blocks((len >> 5) + 1), bit(blocks, 0), sum(blocks, 0) {} void set(int k) { bit[k >> 5]|= 1U << (k & 31); } void build() { for (std::size_t i= 1; i < blocks; i++) sum[i]= sum[i - 1] + __builtin_popcount(bit[i - 1]); zeros= rank0(len); } bool operator[](int k) const { return (bit[k >> 5] >> (k & 31)) & 1; } std::size_t rank(std::size_t k) const { return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1))); } std::size_t rank0(std::size_t k) const { return k - rank(k); } }; std::size_t len, lg; std::vector mat; std::vector vec; public: WaveletMatrix(const std::vector &v): len(v.size()), lg(32 - __builtin_clz(std::max(len, 1))), mat(lg, len), vec(v) { std::sort(vec.begin(), vec.end()); vec.erase(std::unique(vec.begin(), vec.end()), vec.end()); std::vector cur(len), nex(len); for (int i= len; i--;) cur[i]= std::lower_bound(vec.begin(), vec.end(), v[i]) - vec.begin(); for (auto h= lg; h--; cur.swap(nex)) { for (std::size_t i= 0; i < len; i++) if ((cur[i] >> h) & 1) mat[h].set(i); mat[h].build(); std::array it{nex.begin(), nex.begin() + mat[h].zeros}; for (std::size_t i= 0; i < len; i++) *it[mat[h][i]]++= cur[i]; } } // k-th(0-indexed) smallest number in v[l,r) T kth_smallest(int l, int r, int k) const { assert(k < r - l); std::size_t ret= 0; for (auto h= lg; h--;) if (auto l0= mat[h].rank0(l), r0= mat[h].rank0(r); k >= r0 - l0) { k-= r0 - l0, ret|= 1 << h; l+= mat[h].zeros - l0, r+= mat[h].zeros - r0; } else l= l0, r= r0; return vec[ret]; } // k-th(0-indexed) largest number in v[l,r) T kth_largest(int l, int r, int k) const { return kth_smallest(l, r, r - l - k - 1); } // count i s.t. (l <= i < r) && (v[i] < ub) std::size_t count(int l, int r, T ub) const { std::size_t x= std::lower_bound(vec.begin(), vec.end(), ub) - vec.begin(); if (x >= 1u << lg) return r - l; if (x == 0) return 0; std::size_t ret= 0; for (auto h= lg; h--;) if (auto l0= mat[h].rank0(l), r0= mat[h].rank0(r); (x >> h) & 1) ret+= r0 - l0, l+= mat[h].zeros - l0, r+= mat[h].zeros - r0; else l= l0, r= r0; return ret; } // count i s.t. (l <= i < r) && (lb <= v[i] < ub) std::size_t count(int l, int r, T lb, T ub) const { return count(l, r, ub) - count(l, r, lb); } }; using namespace std; struct RSQ { using T= long long; static T ti() { return 0; } static T op(T a, T b) { return a + b; } }; signed main() { cin.tie(0); ios::sync_with_stdio(0); int N, Q; cin >> N >> Q; vector A(N); vector> xyv(N); for (int i= 0; i < N; ++i) cin >> A[i], xyv[i]= {i, A[i], A[i]}; WaveletMatrix wm(A); KDTree kdt(xyv); for (int i= 0; i < Q; ++i) { int L, R; cin >> L >> R, --L; int k= (R - L - 1) / 2; long long u= wm.kth_smallest(L, R, k); long long ans= u * k - kdt.fold_cuboid(L, R - 1, -1e9, u - 1); ans+= kdt.fold_cuboid(L, R - 1, u, 1e9) - u * (R - L - k); cout << ans << '\n'; } return 0; }