#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int nmax = 1e5 + 5;
int a[nmax];
int cnt[nmax];
pair<int, pair<int, int> > cur_with_cnt[nmax];
void add(int i) {
  int v = a[i];
  int c = cnt[v];
  ++cnt[v];
  if (!cur_with_cnt[c + 1].first) {
    cur_with_cnt[c + 1].second = make_pair(c + 1, c + 1);
    int l = cur_with_cnt[c].second.first;
    swap(cur_with_cnt[c].second.first, cur_with_cnt[c + 1].second.first);
    swap(cur_with_cnt[c + 1].second.second, cur_with_cnt[l].second.second);
  }
  --cur_with_cnt[c].first;
  assert(cur_with_cnt[c].first >= 0);
  ++cur_with_cnt[c + 1].first;
  if (!cur_with_cnt[c].first) {
    int l = cur_with_cnt[c].second.second;
    swap(cur_with_cnt[l].second.first, cur_with_cnt[c].second.first);
    swap(cur_with_cnt[c].second.second, cur_with_cnt[c + 1].second.second);
  }
}
void rem(int i) {
  int v = a[i];
  int c = cnt[v];
  --cnt[v];
  if (!cur_with_cnt[c - 1].first) {
    cur_with_cnt[c - 1].second = make_pair(c - 1, c - 1);
    int l = cur_with_cnt[c].second.second;
    swap(cur_with_cnt[l].second.first, cur_with_cnt[c - 1].second.first);
    swap(cur_with_cnt[c - 1].second.second, cur_with_cnt[c].second.second);
  }
  --cur_with_cnt[c].first;
  assert(cur_with_cnt[c].first >= 0);
  ++cur_with_cnt[c - 1].first;
  if (!cur_with_cnt[c].first) {
    int l = cur_with_cnt[c].second.first;
    swap(cur_with_cnt[c - 1].second.first, cur_with_cnt[c].second.first);
    swap(cur_with_cnt[c].second.second, cur_with_cnt[l].second.second);
  }
}
int eval() {
  int res = 0;
  bool leftover = false;
  int lval;
  vector<pair<int, int> > comb;
  int i = cur_with_cnt[0].second.first;
  int j = 0;
  while (i != nmax - 1 || j != comb.size()) {
    int n_i = i;
    int n_j = j;
    int val;
    int c_cnt = 0;
    if (j == comb.size() || (i != nmax - 1 && i <= comb[j].first)) {
      val = i;
      c_cnt += cur_with_cnt[i].first;
      n_i = cur_with_cnt[i].second.first;
    }
    if (i == nmax - 1 || (j != comb.size() && comb[j].first <= i)) {
      val = comb[j].first;
      c_cnt += comb[j].second;
      n_j = j + 1;
    }
    assert(c_cnt);
    if (leftover) {
      res += lval + val;
      comb.emplace_back(lval + val, 1);
      --c_cnt;
    }
    res += val * 2 * (c_cnt / 2);
    if (c_cnt / 2) {
      comb.emplace_back(val * 2, c_cnt / 2);
    }
    c_cnt %= 2;
    leftover = c_cnt;
    lval = val;
    i = n_i;
    j = n_j;
  }
  return res;
}
struct query {
  int l, r;
  int idx;
  bool operator<(const query &o) const {
    if (l / 300 == o.l / 300) {
      if ((l / 300) % 2) {
        return r < o.r;
      }
      return o.r < r;
    }
    return o.l < l;
  }
};
int n, q;
query ques[nmax];
int res[nmax];
int main() {
  cin >> n;
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }
  cur_with_cnt[0] = make_pair(n + 5, make_pair((int)nmax - 1, 0));
  cur_with_cnt[nmax - 1] = make_pair(n + 5, make_pair((int)nmax - 1, 0));
  cin >> q;
  for (int i = 0; i < q; ++i) {
    int l, r;
    scanf("%d %d", &l, &r);
    --l;
    ques[i].l = l;
    ques[i].r = r;
    ques[i].idx = i;
  }
  sort(ques, ques + q);
  int l = 0, r = 0;
  for (int i = 0; i < q; ++i) {
    while (l > ques[i].l) {
      add(--l);
    }
    while (r < ques[i].r) {
      add(r++);
    }
    while (l < ques[i].l) {
      rem(l++);
    }
    while (r > ques[i].r) {
      rem(--r);
    }
    res[ques[i].idx] = eval();
  }
  for (int i = 0; i < q; ++i) {
    printf("%d\n", res[i]);
  }
  return 0;
}
