#include <bits/stdc++.h>
using namespace std;
multiset<int> R, S, T;
multiset<int>::iterator it;
int b[120000], c[120000], d[120000], e[120000], g[120000], v[1200];
long long w[120000];
int i, j, k, l, m, n, o, p, u;
long long s, t;
struct query {
  int l, r, o;
  inline bool operator<(const query t) const {
    if (b[l] != b[t.l])
      return b[l] < b[t.l];
    else
      return r < t.r;
  }
};
query q[120000];
int main() {
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%d", &g[i]);
  scanf("%d", &m);
  for (i = 1; i <= m; i++) scanf("%d%d", &q[i].l, &q[i].r), q[i].o = i;
  p = (int)(ceil(4 * sqrt(n)) + 0.5), o = (n - 1) / p + 1;
  for (i = 1; i <= n; i++) b[i] = (i - 1) / p + 1, v[b[i]]++;
  sort(q + 1, q + m + 1);
  for (i = 1, k = 1; i <= o; i++) {
    if (b[q[k].l] != i) continue;
    for (; (k <= m) && (b[q[k].l] == b[q[k].r]); k++) {
      for (j = q[k].l; j <= q[k].r; j++) d[g[j]]++;
      s = 0;
      for (j = q[k].l; j <= q[k].r; j++)
        if (d[g[j]]) S.insert(d[g[j]]), d[g[j]] = 0;
      while (S.size() > 1) {
        t = 0;
        t = t + *S.begin(), S.erase(S.begin());
        t = t + *S.begin(), S.erase(S.begin());
        s = s + t, S.insert(t);
      }
      w[q[k].o] = s;
      for (j = q[k].l; j <= q[k].r; j++) d[g[j]] = 0;
      S.clear();
    }
    d[0] = n;
    for (j = p * (i - 1) + v[i] + 1; (k <= m) && (b[q[k].l] == i); k++) {
      for (; j <= q[k].r; j++) {
        e[g[j]]++;
        if (e[g[j]] == p + 1)
          d[e[g[j]] - 1]--, T.insert(g[j]);
        else if (e[g[j]] <= p)
          d[e[g[j]] - 1]--, d[e[g[j]]]++;
      }
      for (l = q[k].l; l <= p * (i - 1) + v[i]; l++) {
        e[g[l]]++;
        if (e[g[l]] == p + 1)
          d[e[g[l]] - 1]--, T.insert(g[l]);
        else if (e[g[l]] <= p)
          d[e[g[l]] - 1]--, d[e[g[l]]]++;
      }
      R.clear();
      for (it = T.begin(); it != T.end(); it++) R.insert(e[*it]);
      for (l = 1; l <= p; l++) c[l] = d[l];
      s = 0, t = 0;
      for (l = 1; l <= p; l++)
        if (c[l]) {
          if (t) {
            t = t + l, c[l]--, s = s + t;
            if (t <= p)
              c[t]++;
            else
              R.insert(t);
            t = 0;
          }
          s = s + 1LL * (l + l) * (c[l] / 2);
          if (l + l <= p)
            c[l + l] = c[l + l] + c[l] / 2;
          else
            for (u = 1; u <= c[l] / 2; u++) R.insert(l + l);
          c[l] = c[l] % 2;
          if (c[l]) t = l, c[l] = 0;
        }
      if (t) R.insert(t);
      while (R.size() > 1) {
        t = 0;
        t = t + *R.begin(), R.erase(R.begin());
        t = t + *R.begin(), R.erase(R.begin());
        s = s + t, R.insert(t);
      }
      w[q[k].o] = s;
      for (l = q[k].l; l <= p * (i - 1) + v[i]; l++) {
        e[g[l]]--;
        if (e[g[l]] < p)
          d[e[g[l]]]++, d[e[g[l]] + 1]--;
        else if (e[g[l]] == p)
          d[e[g[l]]]++, T.erase(g[l]);
      }
    }
    memset(d, 0, sizeof(d));
    memset(e, 0, sizeof(e));
    T.clear();
  }
  for (i = 1; i <= m; i++) printf("%I64d\n", w[i]);
  return 0;
}
