#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005, block = 400;
int n, m, ans[MAXN], a[MAXN], num[MAXN];
struct X {
  int l, r, w;
} s[MAXN], f[MAXN];
inline bool cmp(X u, X v) {
  if (u.l / block != v.l / block) return u.l / block < v.l / block;
  return u.r < v.r;
}
inline void add(int x) {
  int u = ++num[x];
  --f[u - 1].w;
  ++f[u].w;
  if (!f[u - 1].w) {
    f[f[u - 1].l].r = f[u - 1].r;
    f[f[u - 1].r].l = f[u - 1].l;
  }
  if (f[u].w == 1) {
    f[u].l = f[f[u - 1].r].l;
    f[u].r = f[u - 1].r;
    f[f[u].l].r = f[f[u].r].l = u;
  }
}
inline void del(int x) {
  int u = --num[x];
  --f[u + 1].w;
  ++f[u].w;
  if (!f[u + 1].w) {
    f[f[u + 1].l].r = f[u + 1].r;
    f[f[u + 1].r].l = f[u + 1].l;
  }
  if (f[u].w == 1) {
    f[u].l = f[u + 1].l;
    f[u].r = f[f[u + 1].l].r;
    f[f[u].l].r = f[f[u].r].l = u;
  }
}
queue<pair<int, int> > q;
int res, now;
inline pair<int, int> pop() {
  pair<int, int> x;
  if (now && (q.empty() || now < q.front().first))
    x = make_pair(now, f[now].w), now = f[now].r;
  else
    x = q.front(), q.pop();
  return x;
}
inline int solve() {
  res = 0;
  now = f[0].r;
  pair<int, int> u, v;
  while (now || !q.empty()) {
    u = pop();
    while (true) {
      if (u.second >= 2) {
        res += (u.first << 1) * (u.second / 2);
        q.push(make_pair(u.first << 1, u.second / 2));
        u.second %= 2;
      }
      if (u.second && (now || !q.empty())) {
        v = pop();
        res += u.first + v.first;
        q.push(make_pair(u.first + v.first, 1));
        --v.second;
        u = v;
      } else
        break;
    }
  }
  return res;
}
int main() {
  scanf("%d", &n);
  for (register int i = 1; i <= n; ++i) scanf("%d", a + i);
  scanf("%d", &m);
  for (register int i = 1; i <= m; ++i) {
    scanf("%d%d", &s[i].l, &s[i].r);
    s[i].w = i;
  }
  sort(s + 1, s + m + 1, cmp);
  for (register int L, R, i = 1; i <= m; ++i) {
    int l = s[i].l, r = s[i].r;
    if (i == 1 || s[i].l / block != s[i - 1].l / block) {
      memset(num, 0, sizeof num);
      memset(f, 0, sizeof(X) * (n + 1));
      f[0].w = n + 5;
      L = l;
      R = l - 1;
    }
    while (R < r) add(a[++R]);
    while (L > l) add(a[--L]);
    while (L < l) del(a[L++]);
    ans[s[i].w] = solve();
  }
  for (register int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
  return 0;
}
