#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int B = 433;
struct Node {
  int l, r, id;
  Node() {}
  void input() { scanf("%d%d", &l, &r); }
  bool operator<(const Node &a) const {
    if (l / B == a.l / B) return r / B < a.r / B;
    return l / B < a.l / B;
  }
} Q[N];
int pre[N], nxt[N], cnt[N], num[N], last;
int n, q, a[N], ans[N], sum[N], que1[N], que2[N], m1, m2;
int L, R;
inline void sub(int x) {
  if (x == 0) return;
  cnt[x]--;
  if (cnt[x] == 0) {
    nxt[pre[x]] = nxt[x];
    pre[nxt[x]] = pre[x];
    if (last == x) last = pre[x];
  }
}
inline void add(int x) {
  if (x == 0) return;
  cnt[x]++;
  if (cnt[x] == 1) {
    nxt[last] = x;
    pre[x] = last;
    nxt[x] = 0;
    last = x;
  }
}
inline int cal() {
  int res = 0;
  for (int i = 1; i <= B; i++) sum[i] = 0;
  int tmp = last;
  m1 = m2 = 0;
  while (tmp) {
    if (tmp <= B)
      sum[tmp] += cnt[tmp];
    else {
      for (int i = 1; i <= cnt[tmp]; i++) que1[++m1] = tmp;
    }
    tmp = pre[tmp];
  }
  for (int i = 1; i <= B;) {
    if (sum[i] == 0)
      i++;
    else if (sum[i] == 1) {
      int j = i + 1;
      while (j <= B) {
        if (sum[j]) {
          sum[i]--;
          sum[j]--;
          if (i + j <= B)
            sum[i + j]++;
          else
            que1[++m1] = i + j;
          res += i + j;
          break;
        }
        j++;
      }
      if (j > B) que1[++m1] = i;
      i = j;
    } else {
      if (2 * i <= B) {
        res += sum[i] / 2 * 2 * i;
        sum[2 * i] += sum[i] / 2;
        sum[i] -= sum[i] / 2 * 2;
      } else {
        res += sum[i] / 2 * 2 * i;
        for (int j = 1; j <= sum[i] / 2; j++) que1[++m1] = 2 * i;
        sum[i] -= sum[i] / 2 * 2;
      }
    }
  }
  sort(que1 + 1, que1 + 1 + m1);
  int h1 = 1, h2 = 1;
  int tmp1, tmp2, flag = 1;
  for (int i = 1, m = m1; i < m; i++) {
    if (h1 <= m1 && (que1[h1] <= que2[h2] || h2 > m2))
      tmp1 = que1[h1], h1++;
    else
      tmp1 = que2[h2], h2++;
    if (h1 <= m1 && (que1[h1] <= que2[h2] || h2 > m2))
      tmp2 = que1[h1], h1++;
    else
      tmp2 = que2[h2], h2++;
    if (flag)
      que2[++m2] = tmp1 + tmp2;
    else
      que1[++m1] = tmp1 + tmp2;
    res += tmp1 + tmp2;
    if (flag && h1 > m1)
      flag = 0;
    else if (!flag && h2 > m2)
      flag = 1;
  }
  return res;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    Q[i].input();
    Q[i].id = i;
  }
  sort(Q + 1, Q + 1 + q);
  L = 1;
  R = 0;
  for (int i = 1; i <= q; i++) {
    while (Q[i].l > L) sub(num[a[L]]), num[a[L]]--, add(num[a[L]]), L++;
    while (Q[i].l < L) L--, sub(num[a[L]]), num[a[L]]++, add(num[a[L]]);
    while (Q[i].r < R) sub(num[a[R]]), num[a[R]]--, add(num[a[R]]), R--;
    while (Q[i].r > R) R++, sub(num[a[R]]), num[a[R]]++, add(num[a[R]]);
    ans[Q[i].id] = cal();
  }
  for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
}
