#include <bits/stdc++.h>
using namespace std;
const int N = 400010;
int n, m, sqr, p;
int a[N], num[N], Big[N], len = 0;
int cnt[N], blt[N];
bool used[N];
struct P {
  int id, l, r, blo;
  inline bool operator<(const P &yy) const {
    return blo != yy.blo ? blo < yy.blo : r < yy.r;
  }
};
P q[N];
int ans[N], tmp[N];
void gi(int &x) {
  x = 0;
  register char c = getchar();
  for (; c < '0' || c > '9'; c = getchar())
    ;
  for (; c >= '0' && c <= '9'; c = getchar())
    x = (x << 1) + (x << 3) + (c ^ 48);
}
inline void add(int x) {
  --blt[cnt[a[x]]], cnt[a[x]] += (used[x] ? -1 : 1);
  ++blt[cnt[a[x]]], used[x] ^= 1;
}
int solve() {
  int sum = 0, flag = 0;
  priority_queue<int, vector<int>, greater<int> > Q;
  for (int i = 1; i <= len; i++)
    if (cnt[Big[i]] >= sqr) Q.push(cnt[Big[i]]);
  for (int i = 1; i < sqr; i++) tmp[i] = blt[i];
  for (int i = 1; i < sqr; i++) {
    if (!tmp[i]) continue;
    if (flag) {
      --tmp[i], sum += i + flag;
      if (i + flag >= sqr)
        Q.push(i + flag);
      else
        ++tmp[i + flag];
      flag = 0;
    }
    if (tmp[i] & 1) flag = i, --tmp[i];
    sum += tmp[i] * i;
    if (i + i >= sqr) {
      for (int j = 1; j + j <= tmp[i]; j++) Q.push(i + i);
    } else
      tmp[i + i] += tmp[i] / 2;
  }
  if (flag) Q.push(flag);
  for (; Q.size() > 1;) {
    int x = Q.top();
    Q.pop();
    int y = Q.top();
    Q.pop();
    sum += x + y, Q.push(x + y);
  }
  return sum;
}
int main() {
  gi(n), sqr = sqrt(n);
  for (int i = 1; i <= n; i++) {
    gi(a[i]), ++num[a[i]];
    if (num[a[i]] == sqr) Big[++len] = a[i];
  }
  gi(m), p = sqrt(n);
  for (int i = 1; i <= m; i++)
    gi(q[i].l), gi(q[i].r), q[i].blo = q[i].l / p, q[i].id = i;
  sort(q + 1, q + m + 1);
  int l = 1, r = 0;
  blt[0] = n;
  for (int i = 1; i <= m; i++) {
    for (; r < q[i].r; add(++r))
      ;
    for (; l > q[i].l; add(--l))
      ;
    for (; r > q[i].r; add(r--))
      ;
    for (; l < q[i].l; add(l++))
      ;
    ans[q[i].id] = solve();
  }
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}
