#include <bits/stdc++.h>
using namespace std;
const int maxn = int(1e5) + 10;
int n, m;
int a[maxn];
int cnt[maxn], num[maxn];
int block, upper;
int over[maxn], tot;
int belong[maxn];
struct query {
  int l, r, id;
  query() {}
  query(int _l, int _r, int _id) : l(_l), r(_r), id(_id) {}
} q[maxn];
bool cmp(const query& a, const query& b) {
  if (belong[a.l] == belong[b.l]) return a.r < b.r;
  return belong[a.l] < belong[b.l];
}
void add(int val, int p) {
  num[cnt[val]]--;
  cnt[val] += p;
  num[cnt[val]]++;
  return;
}
priority_queue<int, vector<int>, greater<int> > que;
int remain = 0, ans = 0;
int tmp[maxn];
void init() {
  while (que.size()) que.pop();
  remain = ans = 0;
  return;
}
int solve() {
  init();
  for (int i = 0; i < tot; i++)
    if (cnt[over[i]] > upper) que.push(cnt[over[i]]);
  for (int i = 1; i <= upper; i++) tmp[i] = num[i];
  for (int i = 1; i <= upper; i++)
    if (tmp[i]) {
      if (remain) {
        int val = remain + i;
        ans += val;
        tmp[i]--;
        remain = 0;
        if (val > upper)
          que.push(val);
        else
          tmp[val]++;
      }
      if (tmp[i] & 1) {
        tmp[i]--;
        remain = i;
      }
      ans += tmp[i] * i;
      int val = i << 1, siz = tmp[i] >> 1;
      if (val > upper) {
        for (int i = 0; i < siz; i++) que.push(val);
      } else
        tmp[val] += siz;
    }
  if (remain) que.push(remain);
  while (que.size() >= 2) {
    int g1 = que.top();
    que.pop();
    int g2 = que.top();
    que.pop();
    ans += g1 + g2;
    que.push(g1 + g2);
  }
  return ans;
}
int main() {
  scanf("%d", &n);
  upper = block = (int)sqrt(n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    cnt[a[i]]++;
    if (cnt[a[i]] == upper) over[tot++] = a[i];
    belong[i] = (i - 1) / block + 1;
  }
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &q[i].l, &q[i].r);
    q[i].id = i;
  }
  sort(q + 1, q + 1 + m, cmp);
  int l = 0, r = 0, ans[maxn];
  memset(cnt, 0, sizeof cnt);
  for (int i = 1; i <= m; i++) {
    int ql = q[i].l, qr = q[i].r;
    while (r < qr) add(a[++r], 1);
    while (r > qr) add(a[r--], -1);
    while (l < ql) add(a[l++], -1);
    while (l > ql) add(a[--l], 1);
    ans[q[i].id] = solve();
  }
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}
