#include <bits/stdc++.h>
using namespace std;
vector<int> st;
int block, n, a[100005], m, f[100005], ans[100005], cnt[100005], num[100005],
    cnt1[100005];
bool vis[100005];
struct query {
  int l, r, block, id;
} q[100005];
inline int read() {
  int x = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x;
}
inline bool cmp(query x, query y) {
  return x.block == y.block ? x.r < y.r : x.block < y.block;
}
inline void update(int x) {
  cnt[f[a[x]]]--;
  if (vis[x])
    f[a[x]]--;
  else
    f[a[x]]++;
  cnt[f[a[x]]]++;
  vis[x] ^= 1;
}
inline int cal() {
  int res = 0, pre = 0;
  priority_queue<int, vector<int>, greater<int> > que;
  for (int i = 0; i < st.size(); ++i)
    if (f[st[i]] > block) que.push(f[st[i]]);
  for (int i = 1; i <= block; ++i) cnt1[i] = cnt[i];
  for (int i = 1; i <= block; ++i)
    if (cnt1[i]) {
      if (pre) {
        cnt1[i]--;
        res += pre + i;
        if (pre + i > block)
          que.push(pre + i);
        else
          cnt1[pre + i]++;
        pre = 0;
      }
      if (cnt1[i] & 1) {
        cnt1[i]--;
        pre = i;
      }
      res += cnt1[i] * i;
      if ((i << 1) > block)
        for (int j = 1; j <= (cnt1[i] >> 1); ++j) que.push(i << 1);
      else
        cnt1[i << 1] += (cnt1[i] >> 1);
    }
  if (pre) que.push(pre);
  while (que.size() > 1) {
    int x1 = que.top();
    que.pop();
    int x2 = que.top();
    que.pop();
    res += x1 + x2;
    que.push(x1 + x2);
  }
  return res;
}
int main() {
  n = read();
  block = sqrt(n);
  for (int i = 1; i <= n; ++i) {
    a[i] = read();
    num[a[i]]++;
    if (num[a[i]] == block) st.push_back(a[i]);
  }
  m = read();
  for (int i = 1; i <= m; ++i) {
    q[i].l = read();
    q[i].r = read();
    q[i].id = i;
    q[i].block = (q[i].l - 1) / block;
  }
  sort(q + 1, q + m + 1, cmp);
  int l = 1, r = 0;
  for (int i = 1; i <= m; ++i) {
    for (; l < q[i].l; ++l) update(l);
    for (; l > q[i].l; --l) update(l - 1);
    for (; r < q[i].r; ++r) update(r + 1);
    for (; r > q[i].r; --r) update(r);
    ans[q[i].id] = cal();
  }
  for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
  return 0;
}
