#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5;
unordered_set<int> s;
int mar[maxn], cnt[maxn], ans[maxn], kl[maxn], a[maxn], ll[maxn], rr[maxn];
pair<pair<int, pair<int, int> >, int> b[maxn];
int n, q;
const int block = 400;
void addd(int i) { kl[i / block]++; }
void delete_(int i) { kl[i / block]--; }
void add(int i) {
  if (mar[a[i]] > 0) {
    cnt[mar[a[i]]]--;
    if (cnt[mar[a[i]]] == 0) delete_(mar[a[i]]);
  }
  mar[a[i]]++;
  cnt[mar[a[i]]]++;
  if (cnt[mar[a[i]]] == 1) addd(mar[a[i]]);
}
void del(int i) {
  if (mar[a[i]] > 0) {
    cnt[mar[a[i]]]--;
    if (cnt[mar[a[i]]] == 0) delete_(mar[a[i]]);
  }
  mar[a[i]]--;
  if (mar[a[i]] > 0) {
    cnt[mar[a[i]]]++;
    if (cnt[mar[a[i]]] == 1) addd(mar[a[i]]);
  }
}
int l1, l2, v;
pair<int, int> qw[20000], st[20000];
pair<int, int> mn() {
  if (l2 > q)
    return st[l1];
  else if (l1 > v)
    return qw[l2];
  else if (st[l1].first < qw[l2].first)
    return st[l1];
  else
    return qw[l2];
}
void delete_mn() {
  if (l2 > q)
    l1++;
  else if (l1 > v)
    l2++;
  else if (st[l1].first < qw[l2].first)
    l1++;
  else
    l2++;
}
void ins(pair<int, int> g) {
  q++;
  qw[q] = g;
}
void backst(pair<int, int> g) {
  l1--;
  st[l1] = g;
}
int count_ans() {
  v = 0;
  q = 0;
  int j = 0;
  for (int i = 0; i <= n; i += block, j++) {
    if (kl[j] == 0) continue;
    int cn = 0;
    for (int l = i; l < i + block; l++) {
      if (l > n) break;
      if (cn == kl[j]) break;
      if (cnt[l] > 0) {
        v++;
        st[v].first = l;
        st[v].second = cnt[l];
        cn++;
      }
    }
  }
  l1 = 1;
  int ans = 0;
  l2 = 1;
  while (v - l1 + 1 + q - l2 + 1 >= 1) {
    pair<int, int> g = mn();
    int sz = v - l1 + 1 + q - l2 + 1;
    if (g.second == 1 && sz == 1) break;
    if (g.second == 1) {
      delete_mn();
      pair<int, int> g2 = mn();
      g2.second--;
      delete_mn();
      int cs = g2.first;
      if (g2.second > 0) backst(g2);
      ans += (g.first + cs);
      ins(make_pair(g.first + cs, 1));
    } else {
      delete_mn();
      int v = g.second / 2;
      ans += 2 * (g.first) * v;
      g.second = g.second % 2;
      if (g.second > 0) backst(make_pair(g.first, 1));
      ins(make_pair(g.first * 2, v));
    }
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n;
  int qq;
  for (int i = 1; i <= n; i++) cin >> a[i];
  cin >> qq;
  for (int i = 1; i <= qq; i++) {
    cin >> ll[i] >> rr[i];
    b[i] = make_pair(make_pair(ll[i] / block, make_pair(rr[i], ll[i])), i);
  }
  sort(b + 1, b + qq + 1);
  int ll = 1;
  int rr = 0;
  for (int i = 1; i <= qq; i++) {
    int nl = b[i].first.second.second;
    int nr = b[i].first.second.first;
    for (; rr < nr; rr++) add(rr + 1);
    for (; rr > nr; rr--) del(rr);
    for (; ll < nl; ll++) del(ll);
    for (; ll > nl; ll--) add(ll - 1);
    ans[b[i].second] = count_ans();
  }
  for (int i = 1; i <= qq; i++) cout << ans[i] << "\n";
  return 0;
}
