#include <bits/stdc++.h>
using namespace std;
int a[101010], L[101010], R[101010], id[101010], N;
int num[101010], sz[101010], cnt[101010], ans[101010];
priority_queue<int, vector<int>, greater<int> > q;
vector<int> vec;
inline void add(int u) { cnt[sz[u]]--, cnt[++sz[u]]++; }
inline void del(int u) { cnt[sz[u]]--, cnt[--sz[u]]++; }
inline int calc() {
  for (int i = 1; i < N; i++) num[i] = cnt[i];
  for (int x : vec)
    if (sz[x] >= N) q.push(sz[x]);
  int ans = 0, val, nn;
  for (int i = 1, nxt = 2; i < N; i++)
    if (num[i]) {
      if (num[i] > 1) {
        nn = num[i] >> 1, ans += i * nn << 1;
        val = i << 1;
        if (val >= N)
          while (nn--) q.push(val);
        else
          num[val] += nn;
        num[i] &= 1;
      }
      if (num[i]) {
        for (num[i] = 0; nxt < N && !num[nxt]; nxt++)
          ;
        if (nxt >= N) {
          q.push(i);
          break;
        }
        num[nxt]--, ans += i + nxt;
        val = nxt + i;
        if (val >= N)
          q.push(val);
        else
          num[val]++;
      }
    }
  while (q.size() > 1) {
    val = q.top();
    q.pop();
    val += q.top();
    q.pop();
    ans += val, q.push(val);
  }
  q.pop();
  return ans;
}
int main() {
  int n;
  scanf("%d", &n);
  N = sqrt(n);
  for (int i = 1; i <= n; i++) scanf("%d", a + i), num[a[i]]++;
  for (int i = 1; i <= n; i++)
    if (num[a[i]] >= N) {
      vec.push_back(a[i]);
      num[a[i]] = 0;
    }
  int q;
  scanf("%d", &q);
  for (int i = 0; i < q; i++) scanf("%d %d", L + i, R + i), id[i] = i;
  sort(id, id + q, [](int u, int v) {
    int A = L[u] / N, B = L[v] / N;
    if (A != B) return A < B;
    if (A & 1) return R[u] < R[v];
    return R[u] > R[v];
  });
  int st = L[id[0]], ed = st - 1;
  for (int i = 0, u; i < q; i++) {
    u = id[i];
    while (ed < R[u]) add(a[++ed]);
    while (ed > R[u]) del(a[ed--]);
    while (st < L[u]) del(a[st++]);
    while (st > L[u]) add(a[--st]);
    ans[u] = calc();
  }
  for (int i = 0; i < q; i++) printf("%d\n", ans[i]);
}
