#include <bits/stdc++.h>
using namespace std;
const int S = 315;
struct O {
  int l, r, i;
} o[100005];
priority_queue<int, vector<int>, greater<int> > Q;
vector<int> D;
int n, m, a[100005], ans[100005], f[100005], g[100005], N[100005];
bool cmp(O a, O b) { return a.l / S == b.l / S ? a.r < b.r : a.l < b.l; }
void add(int u, int o) {
  --f[N[u]];
  ++f[N[u] += o];
}
int qiu() {
  int i, j = 0, ans = 0;
  for (i = 0; i < D.size(); ++i)
    if (N[D[i]] > S) Q.push(N[D[i]]);
  for (i = 1; i <= S; ++i) g[i] = f[i];
  for (i = 1; i <= S; ++i)
    if (g[i]) {
      if (j) {
        --g[i];
        ans += i + j;
        if (i + j > S)
          Q.push(i + j);
        else
          ++g[i + j];
        j = 0;
      }
      if (g[i] & 1) --g[i], j = i;
      ans += g[i] * i;
      if ((i << 1) > S)
        for (int p = g[i] >> 1; p; --p) Q.push(i << 1);
      else
        g[i << 1] += g[i] >> 1;
    }
  if (j) Q.push(j);
  while (!Q.empty()) {
    i = Q.top();
    Q.pop();
    if (Q.empty()) break;
    j = Q.top();
    Q.pop();
    ans += i + j;
    Q.push(i + j);
  }
  return ans;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), ++N[a[i]];
  for (int i = 1; i <= 100000; ++i) {
    if (N[i] > S) D.push_back(i);
    N[i] = 0;
  }
  scanf("%d", &m);
  for (int i = 1; i <= m; ++i) scanf("%d%d", &o[i].l, &o[i].r), o[i].i = i;
  sort(o + 1, o + m + 1, cmp);
  int l = 1, r = 0;
  for (int i = 1; i <= m; ++i) {
    while (r < o[i].r) add(a[++r], 1);
    while (l > o[i].l) add(a[--l], 1);
    while (r > o[i].r) add(a[r--], -1);
    while (l < o[i].l) add(a[l++], -1);
    ans[o[i].i] = qiu();
  }
  for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
  return 0;
}
