#include <bits/stdc++.h>   using namespace std;   void debug_out() { cerr << endl; }   template <typename Head, typename... Tail>   void debug_out(Head H, Tail... T) {     cerr <<     << H;     debug_out(T...);   }   const int INF = 1e9;   const long long MOD = 1e9 + 7;   const int N = 1e5 + 5, MO = 320, SQ = 600;   int n, q, A[N], QL[N], QR[N], P[N], T[N], C[N], K[N], Q[N];   vector<int> B, X, Y;   bool CMP(int i, int j) {     if (QL[i] / MO != QL[j] / MO) return QL[i] < QL[j];     return (QL[i] / MO) % 2 ? QR[i] < QR[j] : QR[i] > QR[j];   }   void Update(int x, int y) { T[C[x]]--, C[x] += y, T[C[x]]++; }   void Insert(int x, int y) {     if (x >= SQ && !K[x]) Y.push_back(x);     K[x] += y;   }   int Huf() {     X.clear(), Y.clear();     for (int i : B)       if (C[i] >= SQ) X.push_back(C[i]), K[C[i]]++;     sort(X.begin(), X.end());     int huf = 0, c = 0, x = 0, y = 0;     for (int i = 1; i < SQ; i++)       if (K[i] + T[i]) {         K[i] += T[i];         if (c) huf += i + c, K[i]--, Insert(i + c, 1), c = 0;         if (K[i] & 1) c = i, K[i]--;         if (K[i]) huf += i * K[i], Insert(i + i, K[i] >> 1), K[i] = 0;       }     while (x < (int)(X.size()) || y < (int)(Y.size())) {       while (x + 1 < (int)(X.size()) && X[x + 1] == X[x]) x++;       while (y + 1 < (int)(Y.size()) && Y[y + 1] == Y[y]) y++;       int i = 0;       if (x == (int)(X.size()))         i = Y[y++];       else if (y == (int)(Y.size()))         i = X[x++];       else if (X[x] < Y[y])         i = X[x++];       else         i = Y[y++];       if (c) huf += i + c, K[i]--, Insert(i + c, 1), c = 0;       if (K[i] & 1) c = i, K[i]--;       if (K[i]) huf += i * K[i], Insert(i + i, K[i] >> 1), K[i] = 0;     }     return huf;   }   int main() {     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);     mt19937 Rnd(time(0));     cin >> n;     for (int i = 0; i < n; i++) cin >> A[i], C[A[i]]++;     for (int i = 0; i < N; i++)       if (C[i] >= SQ) B.push_back(i);     for (int i = 0; i < n; i++) C[A[i]]--;     cin >> q;     for (int i = 0; i < q; i++) cin >> QL[i] >> QR[i], QL[i]--, P[i] = i;     sort(P, P + q, CMP);     int L = 0, R = 0;     for (int i = 0; i < q; i++) {       int l = QL[P[i]], r = QR[P[i]];       while (l < L) Update(A[--L], +1);       while (R < r) Update(A[R++], +1);       while (L < l) Update(A[L++], -1);       while (r < R) Update(A[--R], -1);       Q[P[i]] = Huf();     }     for (int i = 0; i < q; i++) cout << Q[i] << endl;     return 0;   }   