#include <bits/stdc++.h>
using namespace std;
using pi3 = pair<pair<int, int>, int>;
const int N = 1e5 + 10;
const int M = 5 * sqrt(N) + 10;
int a[N], b[N], c[N], d[N], e[N];
pi3 qry[N];
vector<int> big;
inline void add(int first) {
  c[b[first]++]--;
  c[b[first]]++;
}
inline void sub(int first) {
  c[b[first]--]--;
  c[b[first]]++;
}
priority_queue<int, vector<int>, greater<int>> p;
int huffman() {
  int ans = 0;
  for (int i = 1; i <= M; i++) d[i] = c[i];
  for (auto first : big)
    if (b[first] > M) p.push(b[first]);
  for (int i = 1, nxt = 2; i <= M; i++)
    if (d[i]) {
      ans += (d[i] / 2) * 2 * i;
      if (i << 1 > M) {
        for (int j = 2; j <= d[i]; j += 2) p.push(i << 1);
      } else {
        d[i << 1] += d[i] >> 1;
      }
      d[i] &= 1;
      if (d[i]) {
        if (nxt <= i) nxt = i + 1;
        while (nxt <= M && d[nxt] == 0) nxt++;
        if (nxt > M) {
          p.push(i);
          break;
        }
        d[nxt]--;
        ans += i + nxt;
        if (i + nxt > M)
          p.push(i + nxt);
        else
          d[i + nxt]++;
      }
      d[i] = 0;
    }
  for (int fst, snd; p.size() > 1;) {
    fst = p.top();
    p.pop();
    snd = p.top();
    p.pop();
    ans += fst + snd;
    p.push(fst + snd);
  }
  while (!p.empty()) p.pop();
  return ans;
}
int main() {
  int n, q;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    b[a[i]]++;
  }
  for (int i = 0; i < N; i++) {
    if (b[i] > M) big.push_back(i);
  }
  memset(b, 0, sizeof b);
  scanf("%d", &q);
  for (int i = 0, L, R; i < q; i++) {
    scanf("%d %d", &L, &R);
    qry[i] = {{L, R}, i};
  }
  sort(qry, qry + q, [](const pi3& a, const pi3& b) {
    return a.first.first / M != b.first.first / M
               ? a.first.first < b.first.first
               : a.first.second > b.first.second;
  });
  int cl = 1, cr = 0;
  for (int i = 0, L, R; i < q; i++) {
    L = qry[i].first.first;
    R = qry[i].first.second;
    while (cr < R) add(a[++cr]);
    while (cr > R) sub(a[cr--]);
    while (cl < L) sub(a[cl++]);
    while (cl > L) add(a[--cl]);
    e[qry[i].second] = huffman();
  }
  for (int i = 0; i < q; i++) {
    printf("%d\n", e[i]);
  }
  return 0;
}
