#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1, M = 317;
int n, m, Q, bel[N], tmp[N];
int a[N], t[N], g[N], ans[N];
struct Ask {
  int l, r, id;
} k[N];
vector<int> s;
priority_queue<int, vector<int>, greater<int> > q;
inline bool cmp(Ask x, Ask y) {
  return bel[x.l] < bel[y.l] ||
         bel[x.l] == bel[y.l] && ((bel[x.l] & 1) ? (x.r < y.r) : (x.r > y.r));
}
void update(int x, int y) { --g[t[x]], t[x] += y, ++g[t[x]]; }
int query() {
  for (int i = 0; i < s.size(); i++)
    if (t[s[i]] > M) q.push(t[s[i]]);
  for (int i = 1; i <= M; i++) tmp[i] = g[i];
  int sum = 0, oth = 0;
  for (int i = 1; i <= M; i++) {
    if (tmp[i] == 0) continue;
    if (oth) {
      if (i + oth > M)
        q.push(i + oth);
      else
        ++tmp[i + oth];
      --tmp[i];
      sum += i + oth;
      oth = 0;
    }
    if (tmp[i] & 1) --tmp[i], oth = i;
    sum += i * tmp[i];
    if ((i << 1) > M)
      for (int j = tmp[i] >> 1; j; j--) q.push(i << 1);
    else
      tmp[i << 1] += tmp[i] >> 1;
  }
  if (oth) q.push(oth);
  while (!q.empty()) {
    int x = q.top();
    q.pop();
    if (q.empty()) break;
    x = x + q.top();
    q.pop();
    sum += x;
    q.push(x);
  }
  return sum;
}
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - 48;
    ch = getchar();
  }
  return x * f;
}
int main() {
  n = read();
  m = sqrt(n);
  for (int i = 1; i <= n; i++) t[a[i] = read()]++, bel[i] = (i + m - 1) / m;
  for (int i = 1; i < N; i++)
    if (t[i] > M) s.push_back(i);
  for (int i = 1; i < N; i++) t[i] = 0;
  Q = read();
  for (int i = 1; i <= Q; i++) k[i].l = read(), k[i].r = read(), k[i].id = i;
  sort(k + 1, k + Q + 1, cmp);
  for (int l = 1, r = 0, i = 1; i <= Q; i++) {
    while (r < k[i].r) update(a[++r], 1);
    while (l > k[i].l) update(a[--l], 1);
    while (r > k[i].r) update(a[r--], -1);
    while (l < k[i].l) update(a[l++], -1);
    ans[k[i].id] = query();
  }
  for (int i = 1; i <= Q; i++) printf("%d\n", ans[i]);
  return 0;
}
