#include <bits/stdc++.h>
using namespace std;
inline long long getint() {
  long long _x = 0, _tmp = 1;
  char _tc = getchar();
  while ((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
  if (_tc == '-') _tc = getchar(), _tmp = -1;
  while (_tc >= '0' && _tc <= '9') _x *= 10, _x += (_tc - '0'), _tc = getchar();
  return _x * _tmp;
}
inline long long add(long long _x, long long _y,
                     long long _mod = 1000000007ll) {
  long long _ = _x + _y;
  if (_ >= _mod) _ -= _mod;
  return _;
}
inline long long sub(long long _x, long long _y,
                     long long _mod = 1000000007ll) {
  long long _ = _x - _y;
  if (_ < 0) _ += _mod;
  return _;
}
inline long long mul(long long _x, long long _y,
                     long long _mod = 1000000007ll) {
  long long _ = _x * _y;
  if (_ >= _mod) _ %= _mod;
  return _;
}
long long mypow(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 1ll;
  long long _tmp = mypow(_a, _x / 2, _mod);
  _tmp = mul(_tmp, _tmp, _mod);
  if (_x & 1) _tmp = mul(_tmp, _a, _mod);
  return _tmp;
}
long long mymul(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 0ll;
  long long _tmp = mymul(_a, _x / 2, _mod);
  _tmp = add(_tmp, _tmp, _mod);
  if (_x & 1) _tmp = add(_tmp, _a, _mod);
  return _tmp;
}
inline bool equal(double _x, double _y) {
  return _x > _y - 1e-9 && _x < _y + 1e-9;
}
int __ = 1, _cs;
void build() {}
int n, a[101010], q, ql[101010], qr[101010], cnt[101010];
int qq[101010];
set<int> M;
bool cmp(int i, int j) {
  if (ql[i] / 300 != ql[j] / 300) return ql[i] / 300 < ql[j] / 300;
  return ((ql[i] / 300) % 2 ? +1 : -1) * qr[i] <
         ((ql[j] / 300) % 2 ? +1 : -1) * qr[j];
}
void init() {
  n = getint();
  for (int i = 1; i <= n; i++) a[i] = getint();
  q = getint();
  for (int i = 0; i < q; i++) {
    ql[i] = getint();
    qr[i] = getint();
    qq[i] = i;
  }
  sort(qq, qq + q, cmp);
}
int ans[101010], cnt2[101010];
inline void modify(int ptr, int dlt) {
  if (--cnt2[cnt[a[ptr]]] == 0) M.erase(cnt[a[ptr]]);
  cnt[a[ptr]] += dlt;
  if (cnt2[cnt[a[ptr]]]++ == 0) M.insert(cnt[a[ptr]]);
}
pair<int, int> q1[101010], q2[101010];
inline int cal() {
  int f1 = 300, t1 = 300, f2 = 300, t2 = 300;
  for (auto it = M.begin(); it != M.end(); it++) q1[t1++] = {*it, cnt2[*it]};
  int res = 0;
  while (f1 != t1 || f2 != t2) {
    pair<int, int> now;
    if (f1 != t1 && (f2 == t2 || q1[f1].first < q2[f2].first))
      now = q1[f1++];
    else
      now = q2[f2++];
    int fre = now.first;
    int tms = now.second;
    if (tms > 1) {
      res += (tms >> 1) * (fre << 1);
      q2[t2++] = {fre << 1, tms >> 1};
      tms &= 1;
    }
    if (tms == 1) {
      if (f1 == t1 && f2 == t2) return res;
      pair<int, int> nxt;
      if (f1 != t1 && (f2 == t2 || q1[f1].first < q2[f2].first))
        nxt = q1[f1++];
      else
        nxt = q2[f2++];
      int nfre = nxt.first;
      int ntms = nxt.second;
      if (ntms > 1) q2[--f2] = {nfre, ntms - 1};
      q2[t2++] = {fre + nfre, 1};
      res += fre + nfre;
    }
  }
  return res;
}
void solve() {
  int lptr = 1, rptr = 1;
  modify(1, +1);
  for (int _ = 0; _ < q; _++) {
    int i = qq[_];
    while (rptr < qr[i]) modify(++rptr, +1);
    while (rptr > qr[i]) modify(rptr--, -1);
    while (lptr < ql[i]) modify(lptr++, -1);
    while (lptr > ql[i]) modify(--lptr, +1);
    ans[i] = cal();
  }
  for (int i = 0; i < q; i++) printf("%d\n", ans[i]);
}
int main() {
  build();
  while (__--) {
    init();
    solve();
  }
}
