#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1, M = 1500;
int n, size, ss, Q, i, a[N], g[N], f[N], ans[N];
int num, out[M], v[M];
struct que {
  int l, r, p;
} q[N];
bool operator<(const que A, const que B) {
  int x = A.l / size, y = B.l / size;
  return x < y || x == y && A.r < B.r;
}
int read() {
  char c = getchar();
  int k = 0;
  for (; c < 48 || c > 57; c = getchar())
    ;
  for (; c > 47 && c < 58; c = getchar()) k = (k << 3) + (k << 1) + c - 48;
  return k;
}
void write(int x) {
  if (x > 9) write(x / 10);
  putchar(x % 10 + 48);
}
void add(int x, int p) {
  f[g[x]]--;
  g[x] += p;
  f[g[x]]++;
}
int la, ra, lb, rb, qa[M], qb[M];
int get() {
  if (qa[la] < qb[lb] && la <= ra || lb > rb)
    return qa[la++];
  else
    return qb[lb++];
}
int solve() {
  int i, rest = 0, ans = 0;
  la = 1, ra = 0, lb = 1, rb = 0;
  for (i = 1; i <= num; i++)
    if (g[out[i]] > ss) qa[++ra] = g[out[i]];
  sort(qa + 1, qa + ra + 1);
  for (i = 1; i <= ss; i++) v[i] = f[i];
  for (i = 1; i <= ss; i++)
    if (v[i]) {
      if (rest) {
        int k = rest + i;
        ans += k;
        v[i]--;
        if (k > ss)
          qb[++rb] = k;
        else
          v[k]++;
        rest = 0;
      }
      if (v[i] & 1) {
        v[i]--;
        rest = i;
      }
      ans += v[i] * i;
      int k = i << 1, s = v[i] >> 1;
      if (k > ss)
        for (; s--;) qb[++rb] = k;
      else
        v[k] += s;
    }
  int have = ra + rb;
  if (!have) return ans;
  if (rest) qb[--lb] = rest, have++;
  for (have--; have--;) {
    int k = get() + get();
    ans += k;
    qb[++rb] = k;
  }
  return ans;
}
int main() {
  n = read();
  size = sqrt(n);
  ss = sqrt(n);
  for (i = 1; i <= n; i++) {
    g[a[i] = read()]++;
    if (g[a[i]] == ss) out[++num] = a[i];
  }
  for (Q = read(), i = 1; i <= Q; i++) q[i] = (que){read(), read(), i};
  sort(q + 1, q + Q + 1);
  q[0].l = q[1].l;
  q[0].r = q[1].l - 1;
  memset(g, 0, sizeof(g));
  for (i = 1; i <= Q; i++) {
    int ll = q[i - 1].l, rr = q[i - 1].r, l = q[i].l, r = q[i].r;
    for (; ll < l; ll++) add(a[ll], -1);
    for (; l < ll; l++) add(a[l], 1);
    for (; rr > r; rr--) add(a[rr], -1);
    for (; r > rr; r--) add(a[r], 1);
    ans[q[i].p] = solve();
  }
  for (i = 1; i <= Q; i++) write(ans[i]), putchar('\n');
}
