#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O2,no-stack-protector,unroll-loops,fast-math")
const int maxn = 1e5 + 10, maxm = 1e5 + 10, lg = 18, mod = 1e9 + 7, inf = 1e18;
int n, q, a[maxn], ans[maxn], sq, L[maxn], R[maxn], cnt[maxn], tnt[maxn];
vector<int> p, nw;
bool csq(int i, int j) {
  if ((L[i] / sq) != (L[j] / sq)) {
    return (L[i] / sq) < (L[j] / sq);
  }
  if ((L[i] / sq) % 2) {
    return R[i] < R[j];
  }
  return R[i] > R[j];
}
void add(int x) {
  tnt[cnt[x]]--, cnt[x]++, tnt[cnt[x]]++;
  if (tnt[cnt[x]] == 1) {
    nw.push_back(cnt[x]);
  }
}
void rmv(int x) {
  tnt[cnt[x]]--, cnt[x]--;
  if (cnt[x]) {
    tnt[cnt[x]]++;
    if (tnt[cnt[x]] == 1) {
      nw.push_back(cnt[x]);
    }
  }
}
int calc() {
  vector<int> qq, pp, pptt;
  for (auto x : nw)
    if (tnt[x]) qq.push_back(x);
  sort(qq.begin(), qq.end());
  qq.resize(unique(qq.begin(), qq.end()) - qq.begin());
  nw.clear();
  for (auto x : qq) nw.push_back(x);
  int i = 0, j = 0, bg = 0, ret = 0;
  while (i < (int)(qq.size()) || j < (int)(pp.size())) {
    int xx = 0, tt = 0, xx1 = (i == (int)(qq.size()) ? inf : qq[i]),
        xx2 = (j == (int)(pp.size()) ? inf : pp[j]);
    if (xx1 <= xx2) xx = xx1, tt += tnt[xx1], i++;
    if (xx2 <= xx1) xx = xx2, tt += pptt[j], j++;
    if (bg) {
      tt--;
      ret += (bg + xx);
      pp.push_back(bg + xx), pptt.push_back(1);
      bg = 0;
    }
    if (tt > 1) {
      ret += (tt / 2) * 2 * xx;
      pp.push_back(2 * xx), pptt.push_back(tt / 2);
    }
    if (tt % 2) bg = xx;
  }
  return ret;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  sq = sqrt(n);
  for (int i = 1; i <= n; i++) cin >> a[i];
  cin >> q;
  for (int i = 0; i < q; i++) cin >> L[i] >> R[i], p.push_back(i);
  sort(p.begin(), p.end(), csq);
  int l = 1, r = 1;
  cnt[a[1]] = tnt[1] = 1, nw.push_back(1);
  for (auto x : p) {
    while (l > L[x]) add(a[--l]);
    while (r < R[x]) add(a[++r]);
    while (l < L[x]) rmv(a[l++]);
    while (r > R[x]) rmv(a[r--]);
    ans[x] = calc();
  }
  for (int i = 0; i < q; i++) cout << ans[i] << '\n';
  return 0;
}
