#include <bits/stdc++.h>
using namespace std;
const int nmax = 100009;
int now[nmax], cnt[nmax], tot[nmax], whr[nmax], a[nmax], pos[nmax];
int i, n, B, q, l, r, top;
int answer[nmax];
pair<pair<int, int>, int> u[nmax];
bool compare(pair<pair<int, int>, int> p, pair<pair<int, int>, int> q) {
  if (whr[p.first.first] == whr[q.first.first])
    return p.first.second < q.first.second;
  return p.first.first < q.first.first;
}
void change(int p, int t) {
  int x = a[p];
  tot[cnt[x]]--;
  if (tot[cnt[x]] == 0) {
    int q = pos[cnt[x]];
    pos[now[top]] = q;
    now[q] = now[top];
    top--;
  }
  cnt[x] += t;
  tot[cnt[x]]++;
  if (tot[cnt[x]] == 1) {
    pos[cnt[x]] = ++top;
    now[top] = cnt[x];
  }
}
int get() {
  queue<pair<int, int> > p, q;
  vector<int> aux;
  int ret = 0;
  for (int i = 1; i <= top; ++i) {
    if (now[i] == 0) continue;
    aux.push_back(now[i]);
    ret -= now[i] * tot[now[i]];
  }
  sort(aux.begin(), aux.end());
  for (int i = 0; i < aux.size(); ++i) p.push(make_pair(aux[i], tot[aux[i]]));
  while (true) {
    int x, y, xx, yy;
    if (p.size() + q.size() == 1) {
      if (p.size()) x = p.front().first, y = p.front().second;
      if (q.size()) x = q.front().first, y = q.front().second;
      if (y == 1) {
        ret += x;
        break;
      }
    }
    if (!p.size()) {
      x = q.front().first, y = q.front().second;
      q.pop();
    } else {
      if (!q.size()) {
        x = p.front().first, y = p.front().second;
        p.pop();
      } else if (p.size() && q.size()) {
        if (p.front().first < q.front().first) {
          x = p.front().first, y = p.front().second;
          p.pop();
        } else {
          x = q.front().first, y = q.front().second;
          q.pop();
        }
      }
    }
    if (y / 2) q.push(make_pair(x + x, y / 2));
    ret += (y - y % 2) * x;
    if (y % 2) {
      if (!p.size()) {
        xx = q.front().first, yy = q.front().second;
        q.front().second--;
        if (q.front().second == 0) q.pop();
        q.push(make_pair(x + xx, 1));
        ret += x + xx;
        continue;
      }
      if (!q.size()) {
        xx = p.front().first, yy = p.front().second;
        p.front().second--;
        if (p.front().second == 0) p.pop();
        q.push(make_pair(x + xx, 1));
        ret += x + xx;
        continue;
      }
      if (p.size() && q.size()) {
        if (p.front().first < q.front().first) {
          xx = p.front().first, yy = p.front().second;
          p.front().second--;
          if (p.front().second == 0) p.pop();
          q.push(make_pair(x + xx, 1));
          ret += x + xx;
        } else {
          xx = q.front().first, yy = q.front().second;
          q.front().second--;
          if (q.front().second == 0) q.pop();
          q.push(make_pair(x + xx, 1));
          ret += x + xx;
        }
      }
    }
  }
  return ret;
}
int main() {
  scanf("%d", &n);
  for (i = 0; i < n; ++i) scanf("%d", &a[i]);
  B = (int)sqrt(1.0 * n);
  for (i = B; i < n; ++i) whr[i] = whr[i - B] + 1;
  scanf("%d", &q);
  for (i = 0; i < q; ++i) {
    scanf("%d", &u[i].first.first);
    scanf("%d", &u[i].first.second);
    u[i].first.first--, u[i].first.second--;
    u[i].second = i;
  }
  sort(u, u + q, compare);
  l = r = u[0].first.first;
  change(l, +1);
  for (i = 0; i < q; ++i) {
    while (l > u[i].first.first) l--, change(l, +1);
    while (r < u[i].first.second) r++, change(r, +1);
    while (l < u[i].first.first) change(l, -1), l++;
    while (r > u[i].first.second) change(r, -1), r--;
    answer[u[i].second] = get();
  }
  for (i = 0; i < q; ++i) printf("%d\n", answer[i]);
  return 0;
}
