#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
inline long long read() {
  register long long x = 0, f = 1;
  register char c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -1;
  for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
  return x * f;
}
void write(long long x) {
  if (x < 0) x = -x, putchar('-');
  if (x >= 10) write(x / 10);
  putchar(x % 10 + '0');
}
void writeln(long long x) {
  write(x);
  puts("");
}
const int maxn = 1e5 + 233;
int num[maxn], cnt[maxn], tt[maxn], block[maxn];
int a[maxn], limit;
struct node {
  int l, r, id;
  bool operator<(const node &w) const {
    if (block[l] != block[w.l]) return block[l] < block[w.l];
    return (block[l] & 1) ? r < w.r : r > w.r;
  }
} Q[maxn];
int n, m;
map<int, int> M;
void add(int x) {
  cnt[num[x]]--;
  if (num[x] > limit)
    if (--M[num[x]] == 0) M.erase(num[x]);
  cnt[++num[x]]++;
  if (num[x] > limit) M[num[x]]++;
}
void del(int x) {
  cnt[num[x]]--;
  if (num[x] > limit)
    if (--M[num[x]] == 0) M.erase(num[x]);
  cnt[--num[x]]++;
  if (num[x] > limit) M[num[x]]++;
}
inline int ask() {
  int ans = 0;
  priority_queue<int> Q;
  while (!Q.empty()) Q.pop();
  for (auto it = M.begin(); it != M.end(); it++)
    for (int t = it->second; t; t--) Q.push(-it->first);
  for (register int i = (1); i <= int(limit); ++i) tt[i] = cnt[i];
  int last = 0;
  for (register int i = (1); i <= int(limit); ++i)
    if (tt[i]) {
      if (last) {
        if (i + last <= limit) {
          tt[i + last]++;
        } else {
          Q.push(-i - last);
        }
        ans += i + last;
        tt[i]--;
        last = 0;
      }
      ans += (tt[i] / 2) * (i + i);
      if (i + i <= limit)
        tt[i + i] += tt[i] / 2;
      else
        for (int j = 1; j * 2 <= tt[i]; ++j) Q.push(-i - i);
      if (tt[i] & 1) last = i;
      tt[i] = 0;
    }
  if (Q.empty()) return ans;
  if (last) {
    int t = -Q.top();
    Q.pop();
    ans += t + last;
    Q.push(-t - last);
    last = 0;
  }
  while (Q.size() > 1) {
    int t1 = -Q.top();
    Q.pop();
    int t2 = -Q.top();
    Q.pop();
    ans += t1 + t2;
    Q.push(-t1 - t2);
  }
  return ans;
}
int ans[maxn];
int main() {
  n = read();
  limit = sqrt(100 * n);
  int unit = sqrt(n);
  for (register int i = (1); i <= int(n); ++i) a[i] = read();
  for (register int i = (1); i <= int(n); ++i) block[i] = (i - 1) / unit + 1;
  m = read();
  for (register int i = (1); i <= int(m); ++i) {
    Q[i].l = read();
    Q[i].r = read();
    Q[i].id = i;
  }
  sort(Q + 1, Q + 1 + m);
  int l = 1, r = 0;
  for (register int i = (1); i <= int(m); ++i) {
    while (l > Q[i].l) add(a[--l]);
    while (r < Q[i].r) add(a[++r]);
    while (l < Q[i].l) del(a[l++]);
    while (r > Q[i].r) del(a[r--]);
    ans[Q[i].id] = ask();
  }
  for (register int i = (1); i <= int(m); ++i) writeln(ans[i]);
  return 0;
}
