Median_Heaps

#include <iostream>
#include <algorithm>
#include <deque>
#include <cmath>
#include <climits>
#define Nmax 100001
using namespace std;

int n, q, x, block, NM;
int aib[Nmax];
long long aibs[Nmax];
int V[Nmax], S[Nmax], N[Nmax];
long long Rez[Nmax];

struct Queryy {
    int st, dr, pos;
}Q[Nmax];

inline void Update(int pos, int val1, int val2){
    for(int i = pos; i < Nmax; i += i & -i)
        aib[i] += val1,
        aibs[i] += val2;
}
inline long long Query(int pos, int c){
    long long sum = 0, s = 0;

    for(int i = pos; i > 0; i -= i & -i)
        sum += aib[i],
        s += aibs[i];

    if(c == 1)
        return sum;
    else return s;
}

inline bool cmp(int a, int b){ return V[a] < V[b];}

inline bool Querys(Queryy a, Queryy b){
    if(a.dr / block == b.dr / block){
        if(a.dr / block % 2 == 0)
            return a.st > b.st;
        else return a.st < b.st;
    }

    return a.dr / block > b.dr / block;
}
inline void Add(int k){ Update(N[k], 1, V[S[N[k]]]);  }
inline void Del(int k){ Update(N[k], -1, -V[S[N[k]]]); }

inline int Binary_Search(int pos){
    int st = 1, dr = n, ans =  -1;

    while(st <= dr){
        int mid = (st + dr) / 2;

        int q = Query(mid, 1);

        if(q >= pos)
            dr = mid - 1,
            ans = mid;
        else st = mid + 1;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    block = sqrt(n);//!impartitm in blocuri vectorul pentru a putea raspunde mai eficient la query-uri

    for(int i = 1; i <= n; ++i){
        cin >> V[i];
        S[i] = i;
    }

    sort(S + 1, S + 1 + n, cmp); //! sortam indici in functie de V[i] pentru ca numerele sunt mari

    for(int i = 1; i <= n; ++i)
        N[S[i]] = i;  //! N[i] = al catelea numar din sir ar fi V[i] daca era sortat crescator

    cin >> q;

    for(int i = 1;  i <= q; ++i){
        cin >> Q[i].st >> Q[i].dr; //!citim query-urile
        Q[i].pos = i;
    }

    sort(Q + 1, Q + 1 + q, Querys); //!sortam query-urile pentru a raspunde mai eficient la ele

    int st = 1, dr = 0;

    for(int i = 1; i <= q; ++i){
        int s = Q[i].st, d = Q[i].dr;

        while(st < s)
            Del(st++);
        while(st > s)
            Add(--st);
        while(dr < d)
            Add(++dr);
        while(dr > d)
            Del(dr--);

        int poss = (d - s + 2) / 2;
        int ans = Binary_Search(poss);
        long long s1 = Query(n, 2);
        int h1 = Query(n, 1);
        long long s2 = Query(ans, 2);
        int h2 = Query(ans, 1);
        s1 = s1 - s2;
        h1 = h1 - h2;

        Rez[Q[i].pos] = s1 - 1LL * h1 * V[S[ans]] + (-s2 + 1LL * h2 * V[S[ans]]) ;
    }

    for(int i = 1; i <= q; ++i)
        cout << Rez[i] << "\n";

    return 0;
}