#include <bits/stdc++.h>
using namespace std;
const int iinf = 1e9 + 7;
const long long linf = 1ll << 60;
const double dinf = 1e10;
template <typename T>
inline void scf(T &x) {
  bool f = 0;
  x = 0;
  char c = getchar();
  while ((c < '0' || c > '9') && c != '-') c = getchar();
  if (c == '-') {
    f = 1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  if (f) x = -x;
  return;
}
template <typename T1, typename T2>
void scf(T1 &x, T2 &y) {
  scf(x);
  return scf(y);
}
template <typename T1, typename T2, typename T3>
void scf(T1 &x, T2 &y, T3 &z) {
  scf(x);
  scf(y);
  return scf(z);
}
template <typename T1, typename T2, typename T3, typename T4>
void scf(T1 &x, T2 &y, T3 &z, T4 &w) {
  scf(x);
  scf(y);
  scf(z);
  return scf(w);
}
const int N = 1e5 + 100;
const int B = 330;
int n, q_n, Min, Max;
int a[N];
int cnt[N], siz[N], apr[N];
long long ans[N];
vector<int> big;
struct Q {
  int i, l, r;
  Q() {}
  Q(int _i, int _l, int _r) : i(_i), l(_l), r(_r) {}
} q[N];
priority_queue<int, vector<int>, greater<int> > heap;
inline void ins(const int &x) {
  --cnt[apr[x]];
  apr[x]++;
  ++cnt[apr[x]];
  return;
}
inline void del(const int &x) {
  --cnt[apr[x]];
  apr[x]--;
  ++cnt[apr[x]];
  return;
}
inline long long solve() {
  long long ret = 0;
  bool lft = 0;
  int lst = -1;
  for (int i = (1); i <= (B); i++)
    if (siz[i] || cnt[i]) {
      siz[i] += cnt[i];
      if (lft) {
        lft = 0, ret += (long long)lst + (long long)i, siz[i]--;
        if (lst + i <= B)
          siz[i + lst]++;
        else
          heap.push(i + lst);
      }
      if (siz[i] & 1) lft = 1, lst = (long long)i;
      siz[i] >>= 1;
      ret += 2ll * i * siz[i];
      if (i + i <= B)
        siz[i + i] += siz[i], siz[i] = 0;
      else
        for (; siz[i]; --siz[i]) heap.push(i + i);
    };
  if (lft) heap.push(lst);
  for (int x : big)
    if (apr[x] > B) heap.push(apr[x]);
  while ((int)heap.size() > 1) {
    lst = heap.top();
    heap.pop();
    lst += heap.top();
    heap.pop();
    ret += (long long)lst;
    heap.push(lst);
  }
  if ((int)heap.size()) heap.pop();
  return ret;
}
int main() {
  scf(n);
  for (int i = 0; i < (n); i++)
    scf(a[i]), Min = min(Min, a[i]), Max = max(Max, a[i]);
  scf(q_n);
  for (int i = 0; i < (q_n); i++) {
    int l, r;
    scf(l, r);
    --l;
    --r;
    q[i] = Q{i, l, r};
  }
  sort(q, q + q_n, [&](Q x, Q y) {
    return x.l / B == y.l / B ? x.r < y.r : x.l / B < y.l / B;
  });
  for (int i = 0; i < (n); i++) {
    if (apr[a[i]] == B) big.push_back(a[i]);
    apr[a[i]]++;
  }
  memset((apr), (0), sizeof((apr)));
  auto p_q = q;
  int l = p_q->l, r = p_q->r;
  cnt[0] = n;
  for (int i = (l); i <= (r); i++) ins(a[i]);
  ans[p_q->i] = solve();
  for (int _ = 0; _ < (q_n - 1); _++) {
    ++p_q;
    while (l > p_q->l) ins(a[--l]);
    while (r < p_q->r) ins(a[++r]);
    while (l < p_q->l) del(a[l++]);
    while (r > p_q->r) del(a[r--]);
    ans[p_q->i] = solve();
  }
  for (int i = 0; i < (q_n); i++) printf("%I64d\n", ans[i]);
  return 0;
}
