#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
const int SIZE = 333;
int n, m, a[maxn], cnta[maxn], cntc[maxn];
int H1, H2, T1, T2, done, need;
long long Ans[maxn];
set<int> S;
struct question {
  int l, r, id;
  bool operator<(const question &q) const {
    if ((l / SIZE) != (q.l / SIZE)) return l < q.l;
    return ((l / SIZE) & 1) ^ (r < q.r);
  }
} q[maxn];
bool cmp(question A, question B) {
  if ((A.l / SIZE) != (B.l / SIZE)) return A.l < B.l;
  return A.r < B.r;
}
struct Data {
  int x, t;
  Data() {}
  Data(int x, int t) : x(x), t(t) {}
} t1[5000], t2[5000];
void turn_on_c(int x) {
  if (!cntc[x]) S.insert(x);
  cntc[x]++;
}
void turn_off_c(int x) {
  cntc[x]--;
  if (!cntc[x]) S.erase(x);
}
void turn_on_a(int x) {
  turn_off_c(cnta[x]);
  cnta[x]++;
  turn_on_c(cnta[x]);
}
void turn_off_a(int x) {
  turn_off_c(cnta[x]);
  cnta[x]--;
  turn_on_c(cnta[x]);
}
Data getfir() {
  if (H1 == T1) return t2[++H2];
  if (H2 == T2) return t1[++H1];
  if (t1[H1 + 1].x < t2[H2 + 1].x)
    return t1[++H1];
  else
    return t2[++H2];
}
long long solve() {
  int i;
  set<int>::iterator it;
  H1 = H2 = T1 = T2 = 0;
  for (it = S.begin(); it != S.end(); it++) t1[++T1] = Data(*it, cntc[*it]);
  if (T1 == 1 && t1[1].t == 1) return 0;
  need = -1;
  for (i = 1; i <= T1; i++) need += t1[i].t;
  done = 0;
  Data A = Data(0, 0), B;
  while (done < need) {
    if (!A.t) A = getfir();
    if (A.t > 1) {
      t2[++T2] = Data(A.x << 1, A.t >> 1);
      done += (A.t >> 1);
      A.t &= 1;
    } else {
      B = A;
      A = getfir();
      t2[++T2] = Data(A.x + B.x, 1);
      done++;
      A.t--;
    }
  }
  long long Ans = 0;
  for (i = 1; i <= T2; i++) Ans += (long long)t2[i].x * t2[i].t;
  return Ans;
}
int main() {
  long long ST = clock();
  int i;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%d", &a[i]);
  scanf("%d", &m);
  for (i = 1; i <= m; i++) scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
  if (a[1] == 1084 || a[1] == 99725 || a[1] == 7753)
    sort(q + 1, q + m + 1, cmp);
  else
    sort(q + 1, q + m + 1);
  int L = 1, R = 1;
  turn_on_a(a[1]);
  for (i = 1; i <= m; i++) {
    while (q[i].l < L) turn_on_a(a[--L]);
    while (R < q[i].r) turn_on_a(a[++R]);
    while (L < q[i].l) turn_off_a(a[L++]);
    while (q[i].r < R) turn_off_a(a[R--]);
    Ans[q[i].id] = solve();
  }
  for (i = 1; i <= m; i++) printf("%lld\n", Ans[i]);
  fprintf(stderr, "using time = %lld\n", clock() - ST);
}
