#include <bits/stdc++.h>
long long gi() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) f ^= ch == '-', ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return f ? x : -x;
}
std::mt19937 rnd(time(NULL));
template <class T>
void cxk(T& a, T b) {
  a = a > b ? a : b;
}
template <class T>
void cnk(T& a, T b) {
  a = a < b ? a : b;
}
struct ques {
  int l, r, i, lb;
} s[100010];
int a[100010], c[100010], cnt[100010], ccnt[100010], sp[100010], cc[100010];
long long ans[100010];
struct pr {
  int fi, se;
};
bool operator<(const pr& a, const pr& b) { return a.fi < b.fi; }
bool operator==(const pr& a, const pr& b) {
  return a.fi == b.fi && a.se == b.se;
}
struct fuck {
  pr S[100010];
  int N;
  void pushup(int p) {
    while (p > 1)
      if (S[p] < S[p >> 1])
        std::swap(S[p], S[p >> 1]), p >>= 1;
      else
        break;
  }
  void pushdown() {
    int p = 1;
    while ((p << 1) <= N) {
      pr MIN = S[p << 1];
      if ((p << 1 | 1) <= N) cnk(MIN, S[p << 1 | 1]);
      if (S[p] < MIN) break;
      if (S[p << 1] == MIN)
        std::swap(S[p << 1], S[p]), p <<= 1;
      else
        std::swap(S[p << 1 | 1], S[p]), p = p << 1 | 1;
    }
  }
  pr top() { return S[1]; }
  void push(pr x) {
    S[++N] = x;
    pushup(N);
  }
  void pop() { S[1] = S[N--], pushdown(); }
  bool empty() { return !N; }
  int size() { return N; }
} que;
int main() {
  int n = gi(), B = 320;
  for (int i = 1; i <= n; ++i) ++c[a[i] = gi()];
  for (int i = 1; i <= 100000; ++i)
    if (c[i] > B) sp[++*sp] = i;
  int Q = gi();
  for (int i = 1; i <= Q; ++i)
    s[i].l = gi(), s[i].r = gi(), s[i].i = i, s[i].lb = s[i].l / B;
  std::sort(s + 1, s + Q + 1, [](ques a, ques b) {
    if (a.lb ^ b.lb) return a.lb < b.lb;
    if (a.lb & 1) return (a.r < b.r);
    return a.r > b.r;
  });
  int L = 1, R = 0;
  auto ins = [&](int x) {
    x = a[x], --ccnt[cnt[x]];
    ++cnt[x];
    ++ccnt[cnt[x]];
  };
  auto del = [&](int x) {
    x = a[x], --ccnt[cnt[x]];
    --cnt[x];
    ++ccnt[cnt[x]];
  };
  double t = 0;
  for (int i = 1; i <= Q; ++i) {
    while (L > s[i].l) ins(--L);
    while (R < s[i].r) ins(++R);
    while (L < s[i].l) del(L++);
    while (R > s[i].r) del(R--);
    while (!que.empty()) que.pop();
    long long res = 0;
    for (int j = B + 1; j <= B + B; ++j) cc[j] = 0;
    for (int j = 1; j <= B; ++j) cc[j] = ccnt[j];
    for (int j = 1, k; j <= B; j = k) {
      res += 2ll * j * (cc[j] >> 1);
      cc[j * 2] += cc[j] >> 1;
      k = j + 1;
      cc[j] &= 1;
      if (cc[j] & 1) {
        while (!cc[k] && k < B) ++k;
        if (k <= B && cc[k]) --cc[j], --cc[k], ++cc[j + k], res += j + k;
      }
    }
    for (int j = 1; j <= B + B; ++j)
      if (cc[j]) que.push({j, cc[j]});
    for (int j = 1; j <= *sp; ++j)
      if (cnt[sp[j]] > B) que.push({cnt[sp[j]], 1});
    while (1) {
      pr x = que.top();
      que.pop();
      if (x.se >= 2) {
        que.push({x.fi * 2, x.se >> 1}), res += 1ll * x.fi * 2 * (x.se >> 1);
        if (x.se & 1) {
          if (que.empty()) break;
          pr y = que.top();
          que.pop();
          que.push({x.fi + y.fi, 1});
          res += x.fi + y.fi;
          if (y.se > 1) que.push({y.fi, y.se - 1});
        }
      } else {
        if (que.empty()) break;
        pr y = que.top();
        que.pop();
        que.push({x.fi + y.fi, 1});
        res += x.fi + y.fi;
        if (y.se > 1) que.push({y.fi, y.se - 1});
      }
    }
    ans[s[i].i] = res;
  }
  for (int i = 1; i <= Q; ++i) printf("%lld\n", ans[i]);
  return 0;
}
