#include <bits/stdc++.h>
using namespace std;
int n, qc;
int a[101010];
pair<pair<int, int>, int> q[101010];
long long int ret[101010];
int s = 300;
int x = 0;
int y = 0;
int cnt[101010];
int nmb[101010];
constexpr int M = 101010 >> 6;
uint64_t mask[M];
set<int> X;
void off(int i) { mask[i >> 6] &= ~((uint64_t)1 << (i & 63)); }
void on(int i) { mask[i >> 6] |= (uint64_t)1 << (i & 63); }
void incr(int c) {
  --nmb[cnt[c]];
  if (nmb[cnt[c]] == 0) off(cnt[c]);
  ++cnt[c];
  if (nmb[cnt[c]] == 0) on(cnt[c]);
  ++nmb[cnt[c]];
}
void decr(int c) {
  --nmb[cnt[c]];
  if (nmb[cnt[c]] == 0) off(cnt[c]);
  --cnt[c];
  if (nmb[cnt[c]] == 0) on(cnt[c]);
  ++nmb[cnt[c]];
}
int main() {
  cin.sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    --a[i];
  }
  cin >> qc;
  for (int i = 0; i < qc; ++i) {
    cin >> q[i].first.first >> q[i].first.second;
    --q[i].first.first;
    q[i].second = i;
  }
  sort(q, q + qc, [](pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
    if (a.first.first / s != b.first.first / s)
      return a.first.first < b.first.first;
    return a.first.second < b.first.second;
  });
  deque<pair<int, int>> A;
  deque<pair<int, int>> B;
  for (int i = 0; i < qc; ++i) {
    int xt = q[i].first.first;
    int yt = q[i].first.second;
    int qi = q[i].second;
    while (xt < x) {
      --x;
      incr(a[x]);
    }
    while (yt > y) {
      incr(a[y]);
      ++y;
    }
    while (xt > x) {
      decr(a[x]);
      ++x;
    }
    while (yt < y) {
      --y;
      decr(a[y]);
    }
    long long int res = 0;
    for (int i = 0; i < M; ++i) {
      uint64_t x = mask[i];
      while (x) {
        int j = __builtin_ctzll(x);
        x ^= (uint64_t)1 << j;
        int k = 64 * i + j;
        A.emplace_back(k, nmb[k]);
      }
    }
    while (!A.empty() || !B.empty()) {
      if (!A.empty() && !B.empty() && (A.front().first == B.front().first)) {
        A.front().second += B.front().second;
        B.pop_front();
      }
      deque<pair<int, int>>& Q =
          (!A.empty() && (B.empty() || A.front().first < B.front().first)) ? A
                                                                           : B;
      pair<int, int>& p = Q.front();
      if (p.second == 1) {
        Q.pop_front();
        if (!(A.empty() && B.empty())) {
          deque<pair<int, int>>& Q2 =
              (!A.empty() && (B.empty() || A.front().first < B.front().first))
                  ? A
                  : B;
          pair<int, int>& p2 = Q2.front();
          res += p.first + p2.first;
          B.emplace_back(p.first + p2.first, 1);
          if (p2.second == 1) {
            Q2.pop_front();
          } else {
            --p2.second;
          }
        }
      } else {
        B.emplace_back(2 * p.first, p.second / 2);
        res += 2 * ((long long int)p.second / 2) * (long long int)p.first;
        if (p.second & 1) {
          p.second = 1;
        } else {
          Q.pop_front();
        }
      }
    }
    ret[qi] = res;
  }
  for (int i = 0; i < qc; ++i) {
    cout << ret[i] << '\n';
  }
  return 0;
}
