#include <bits/stdc++.h>
using namespace std;
struct Storage {
  int typeCnt[100000], numCnt[100000 + 1];
  pair<int, int> span[100000 + 1];
  vector<int> large;
  Storage() {}
  void increase(int ind) {
    int num = typeCnt[ind];
    typeCnt[ind]++;
    numCnt[num]--;
    numCnt[num + 1]++;
    if (num >= 400) {
      int ind = span[num].first;
      large[ind]++;
      span[num].first++;
      span[num + 1].second++;
    } else if (num + 1 == 400) {
      span[num + 1].second++;
      large.push_back(num + 1);
    }
  }
  void decrease(int ind) {
    int num = typeCnt[ind];
    typeCnt[ind]--;
    numCnt[num]--;
    numCnt[num - 1]++;
    if (num - 1 >= 400) {
      int ind = span[num].second - 1;
      large[ind]--;
      span[num].second--;
      span[num - 1].first--;
    } else if (num == 400) {
      span[num].second--;
      large.pop_back();
    }
  }
  int query() {
    vector<int> scnt(400, 0);
    for (int i = 0; i < 400; i++) scnt[i] = numCnt[i];
    int ret = 0;
    vector<int> final;
    {
      vector<int> tmp;
      int last = -1;
      for (int i = 1; i < 400; i++)
        if (scnt[i] != 0) {
          if (last != -1) {
            ret += i + last;
            if (i + last >= 400)
              tmp.push_back(i + last);
            else
              scnt[i + last]++;
            scnt[i]--;
            last = -1;
          }
          if (2 * i >= 400)
            for (int j = 0; j < scnt[i] / 2; j++) tmp.push_back(2 * i);
          else
            scnt[2 * i] += scnt[i] / 2;
          ret += (scnt[i] / 2) * (2 * i);
          if (scnt[i] % 2) last = i;
        }
      if (last != -1) tmp.insert(tmp.begin(), last);
      final.insert(final.end(), large.begin(), large.end());
      final.insert(final.end(), tmp.begin(), tmp.end());
    }
    sort(final.begin(), final.end());
    vector<int> final2;
    for (int i = 0, j = 0; i < (int) final.size() || j < (int)final2.size();) {
      vector<int> toCombine;
      for (int times = 0; times < 2; times++) {
        if (i < (int) final.size() &&
            (j == (int)final2.size() || final[i] < final2[j]))
          toCombine.push_back(final[i++]);
        else if (j < (int)final2.size())
          toCombine.push_back(final2[j++]);
      }
      if (toCombine.size() == 2) {
        ret += toCombine[0] + toCombine[1];
        final2.push_back(toCombine[0] + toCombine[1]);
      }
    }
    return ret;
  }
} storage;
bool opsort(pair<pair<int, int>, int> l, pair<pair<int, int>, int> r) {
  if (l.first.first / 400 != r.first.first / 400)
    return l.first.first < r.first.first;
  return l.first.second < r.first.second;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[i]--;
  }
  int q;
  cin >> q;
  vector<pair<pair<int, int>, int> > op(q);
  vector<int> result(q);
  for (int i = 0; i < q; i++) {
    cin >> op[i].first.first >> op[i].first.second;
    op[i].first.first--;
    op[i].second = i;
  }
  sort(op.begin(), op.end(), opsort);
  pair<int, int> cspan = make_pair(0, 0);
  for (auto cop : op) {
    while (cspan.first < cop.first.first) storage.decrease(a[cspan.first++]);
    while (cspan.first > cop.first.first) storage.increase(a[--cspan.first]);
    while (cspan.second < cop.first.second) storage.increase(a[cspan.second++]);
    while (cspan.second > cop.first.second) storage.decrease(a[--cspan.second]);
    result[cop.second] = storage.query();
  }
  for (auto c : result) cout << c << '\n';
  return 0;
}
