#include <bits/stdc++.h>
using namespace std;
inline void read(int &x) {
  x = 0;
  int f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  x *= f;
}
inline void judge() {
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
}
const int maxn = 100005;
int cnt[maxn], sum[maxn], a[maxn], n, q, sz, bl[maxn];
long long ans[maxn];
struct info {
  int l, r, pr;
  friend inline bool operator<(const info &a, const info &b) {
    return (bl[a.l] < bl[b.l] || (bl[a.l] == bl[b.l] && a.r < b.r));
  }
  inline void in() {
    read(l);
    read(r);
  }
} Q[maxn];
multiset<int> bg;
inline void add(int x) {
  if (sum[a[x]] == sz) {
    bg.insert(sz + 1);
    cnt[sz]--;
    sum[a[x]]++;
    return;
  }
  if (sum[a[x]] < sz) {
    cnt[sum[a[x]]]--;
    cnt[++sum[a[x]]]++;
    return;
  } else {
    bg.erase(bg.find(sum[a[x]]));
    bg.insert(++sum[a[x]]);
  }
}
inline void del(int x) {
  if (sum[a[x]] == sz + 1) {
    bg.erase(bg.find(sz + 1));
    cnt[--sum[a[x]]]++;
    return;
  }
  if (sum[a[x]] <= sz) {
    cnt[sum[a[x]]]--;
    cnt[--sum[a[x]]]++;
    return;
  } else {
    bg.erase(bg.find(sum[a[x]]));
    bg.insert(--sum[a[x]]);
  }
}
int nowl, nowr;
int tmp[maxn];
priority_queue<int, vector<int>, greater<int> > heap;
int main() {
  read(n);
  for (int i = (1); i <= (n); i++) read(a[i]);
  read(q);
  sz = 1000;
  for (int i = (1); i <= (n); i++) bl[i] = i / sz + 1;
  for (int i = (1); i <= (q); i++) Q[i].in(), Q[i].pr = i;
  sort(Q + 1, Q + 1 + q);
  nowl = 1, nowr = 0;
  for (int i = (1); i <= (q); i++) {
    while (nowr < Q[i].r) add(++nowr);
    while (nowr > Q[i].r) del(nowr--);
    while (nowl > Q[i].l) add(--nowl);
    while (nowl < Q[i].l) del(nowl++);
    while (!heap.empty()) heap.pop();
    int lst = 0;
    for (auto it : bg) heap.push(it);
    long long res = 0;
    for (int i = (0); i <= (sz); i++) tmp[i] = cnt[i];
    for (int i = (1); i <= (sz); i++) {
      if (!cnt[i]) continue;
      if (lst) {
        res += i + lst;
        if (i + lst <= sz)
          cnt[i + lst]++;
        else
          heap.push(i + lst);
        cnt[i]--;
        lst = 0;
      }
      res += (i + i) * (cnt[i] / 2);
      if (i + i <= sz)
        cnt[i + i] += cnt[i] / 2;
      else
        for (int k = (1); k <= (cnt[i] / 2); k++) heap.push(i + i);
      if (cnt[i] & 1) lst = i;
    }
    if (lst) heap.push(lst);
    while (heap.size() != 1 && heap.size() != 0) {
      int x = heap.top();
      heap.pop();
      int y = heap.top();
      heap.pop();
      heap.push(x + y);
      res += x + y;
    }
    ans[Q[i].pr] = res;
    for (int i = (0); i <= (sz); i++) cnt[i] = tmp[i];
  }
  for (int i = (1); i <= (q); i++) printf("%I64d\n", ans[i]);
  fprintf(stderr, "ok\n");
  ;
  return 0;
}
