#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int K = 300 + 5;
int n, m;
int a[N], ans[N], w[N], cnt[N], tmp[N];
vector<int> big;
void add(int x, int v) {
  x = a[x];
  cnt[w[x]]--;
  w[x] += v;
  cnt[w[x]]++;
}
int solve() {
  for (int i = 1; i <= K; i++) tmp[i] = cnt[i];
  for (auto i : big) tmp[i] = cnt[i];
  priority_queue<int> Q;
  int ans = 0, rem = 0;
  for (int i = 1; i <= K; i++) {
    if (!cnt[i]) continue;
    if (rem) {
      ans += rem + i;
      cnt[i]--;
      if (rem + i <= K)
        cnt[rem + i]++;
      else
        Q.push(-(rem + i));
      rem = 0;
    }
    int c = cnt[i] / 2;
    ans += c * 2 * i;
    cnt[i] %= 2;
    if (i + i <= K)
      cnt[i + i] += c;
    else {
      while (c) {
        Q.push(-(i + i));
        c--;
      }
    }
    if (cnt[i]) rem = i;
  }
  if (rem) Q.push(-rem);
  for (auto x : big)
    if (w[x] > K) Q.push(-w[x]);
  while (Q.size() >= 2) {
    int x = Q.top();
    Q.pop();
    int y = Q.top();
    Q.pop();
    ans -= x + y;
    Q.push(x + y);
  }
  for (int i = 1; i <= K; i++) cnt[i] = tmp[i];
  for (auto i : big) cnt[i] = tmp[i];
  return ans;
}
int main() {
  scanf("%d", &n);
  map<int, int> M;
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    M[a[i]]++;
  }
  for (auto x : M)
    if (x.second >= K) big.push_back(x.first);
  scanf("%d", &m);
  vector<pair<pair<pair<int, int>, pair<int, int> >, int> > v;
  for (int i = 1; i <= m; i++) {
    int l, r;
    scanf("%d %d", &l, &r);
    v.push_back({{{l / K, r}, {l, r}}, i});
  }
  sort(v.begin(), v.end());
  int L = 1, R = 0;
  for (auto tmp : v) {
    int l, r, i;
    tie(l, r) = tmp.first.second;
    while (L > l) add(--L, +1);
    while (R < r) add(++R, +1);
    while (L < l) add(L++, -1);
    while (R > r) add(R--, -1);
    i = tmp.second;
    ans[i] = solve();
  }
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}
