#include <bits/stdc++.h>
using namespace std;
int v[200100];
int n, m;
long long ans[200100];
struct qu {
  int l, r, id;
  qu() {}
  bool operator<(qu a) const {
    if (l / 1000 != a.l / 1000) return l / 1000 < a.l / 1000;
    return r < a.r;
  }
} q[200100];
int ativo[200100];
int freq[200100];
map<int, int> s;
map<int, int>::iterator it;
int o[1000 + 100], ot[1000 + 100];
void up(int pos) {
  if (!ativo[pos]) {
    if (freq[v[pos]]) {
      if (freq[v[pos]] > 1000) {
        it = s.find(freq[v[pos]]);
        it->second--;
        if (!it->second) s.erase(it);
      } else
        o[freq[v[pos]]]--;
    }
    freq[v[pos]]++;
    if (freq[v[pos]] > 1000)
      s[freq[v[pos]]]++;
    else
      o[freq[v[pos]]]++;
  } else {
    if (freq[v[pos]] > 1000) {
      it = s.find(freq[v[pos]]);
      it->second--;
      if (!it->second) s.erase(it);
    } else
      o[freq[v[pos]]]--;
    freq[v[pos]]--;
    if (freq[v[pos]]) {
      if (freq[v[pos]] > 1000)
        s[freq[v[pos]]]++;
      else
        o[freq[v[pos]]]++;
    }
  }
  ativo[pos] ^= 1;
}
long long get() {
  long long tot = 0;
  map<int, int> q = s;
  int carry = 0, id;
  memcpy(ot, o, sizeof o);
  for (int i = 1; i <= 1000; ++i) {
    if (!o[i]) continue;
    if (carry) {
      tot += (i + id);
      o[i]--;
      if (i + id > 1000)
        q[i + id]++;
      else
        o[i + id]++;
      carry = 0;
    }
    if (o[i] == 1) {
      carry = 1;
      id = i;
    } else if (o[i]) {
      if (2 * i > 1000)
        q[2 * i] += o[i] / 2;
      else
        o[2 * i] += o[i] / 2;
      tot += 2LL * i * (o[i] / 2);
      o[i] = o[i] & 1;
      if (o[i]) i--;
    }
  }
  if (carry) q[id]++;
  memcpy(o, ot, sizeof ot);
  while (q.size()) {
    pair<int, int> x = *q.begin();
    q.erase(q.begin());
    if (q.empty() && x.second == 1) break;
    if (x.second == 1) {
      pair<int, int> y = *q.begin();
      q.erase(q.begin());
      q[x.first + y.first]++;
      tot += x.first + y.first;
      y.second--;
      if (y.second) q[y.first] += y.second;
    } else {
      q[2 * x.first] += x.second / 2;
      int qtd = x.second / 2 * 2;
      tot += (2LL * x.first) * (x.second / 2);
      x.second -= qtd;
      if (x.second) q[x.first] += x.second;
    }
  }
  return tot;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &v[i]);
  }
  scanf("%d", &m);
  for (int i = 0; i < m; ++i) {
    scanf("%d %d", &q[i].l, &q[i].r);
    q[i].id = i;
  }
  sort(q, q + m);
  int l = 1, r = 0;
  for (int i = 0; i < m; ++i) {
    while (q[i].l < l) up(--l);
    while (r < q[i].r) up(++r);
    while (l < q[i].l) up(l++);
    while (q[i].r < r) up(r--);
    ans[q[i].id] = get();
  }
  for (int i = 0; i < m; ++i) {
    printf("%lld\n", ans[i]);
  }
  return 0;
}
