#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int M = 1000;
const int S = 1000;
int res[MAXN], a[MAXN], C[MAXN], d[MAXN], cnt[MAXN];
vector<int> X;
struct Query {
  int idx, l, r;
} Q[MAXN];
inline bool cmp(Query x, Query y) {
  if (x.l / S != y.l / S) return x.l / S < y.l / S;
  return x.r < y.r;
}
void upd(int x, int y) {
  cnt[d[x]]--;
  d[x] += y;
  cnt[d[x]]++;
}
int n, m;
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    C[a[i]]++;
    if (C[a[i]] == M) X.push_back(a[i]);
  }
  scanf("%d", &m);
  for (int i = 0; i < m; i++) scanf("%d%d", &Q[i].l, &Q[i].r), Q[i].idx = i;
  sort(Q, Q + m, cmp);
  int l = 1, r = 0;
  for (int k = 0; k < m; k++) {
    while (r < Q[k].r) upd(a[++r], 1);
    while (l < Q[k].l) upd(a[l++], -1);
    while (Q[k].r < r) upd(a[r--], -1);
    while (Q[k].l < l) upd(a[--l], 1);
    int p = 0, v = 0;
    priority_queue<int> q;
    for (auto &t : X)
      if (d[t] >= M) q.push(-d[t]);
    for (int i = 1; i < M; i++) C[i] = cnt[i];
    for (int i = 1; i < M; i++) {
      if (C[i] == 0) continue;
      if (p != 0) {
        v = p + i;
        C[i]--;
        res[Q[k].idx] += v;
        if (v >= M)
          q.push(-v);
        else
          C[v]++;
        p = 0;
      }
      if (C[i] & 1) p = i, C[i]--;
      res[Q[k].idx] += i * C[i];
      v = i * 2;
      if (v >= M)
        for (int j = 0; j < C[i] / 2; j++) q.push(-v);
      else
        C[v] += C[i] / 2;
    }
    if (p != 0) q.push(-p);
    while (q.size() > 1) {
      int x = -q.top();
      q.pop();
      int y = -q.top();
      q.pop();
      res[Q[k].idx] += x + y;
      q.push(-(x + y));
    }
  }
  for (int i = 0; i < m; i++) printf("%d\n", res[i]);
}
