#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void checkmin(T &a, T b) {
  if (b < a) {
    a = b;
  }
}
template <typename T>
inline void checkmax(T &a, T b) {
  if (b > a) {
    a = b;
  }
}
const int maxn = 123456;
const int BLOCK_SIZE = 300;
struct Query {
  int l, r, id;
  Query(int l, int r, int id) : l(l), r(r), id(id) {}
  Query() {}
  bool operator<(const Query &o) const {
    if (l / BLOCK_SIZE == o.l / BLOCK_SIZE) {
      return r < o.r;
    }
    return l / BLOCK_SIZE < o.l / BLOCK_SIZE;
  }
};
vector<Query> queries;
int a[maxn];
int cnt[1 << 20];
int tot[maxn];
int link_prev[maxn], link_next[maxn];
long long results[maxn];
inline void remove(int a) {
  if (a > 0) {
    link_next[link_prev[a]] = link_next[a];
    link_prev[link_next[a]] = link_prev[a];
    link_next[a] = link_prev[a] = 0;
  }
}
inline void insert(int a) {
  if (a > 0) {
    link_prev[a] = maxn - 1;
    link_next[a] = link_next[maxn - 1];
    link_prev[link_next[a]] = a;
    link_next[maxn - 1] = a;
  }
}
inline void add(int at, int delta) {
  int &cnts = cnt[a[at]];
  if (--tot[cnts] == 0) {
    remove(cnts);
  }
  cnts += delta;
  if (++tot[cnts] == 1) {
    insert(cnts);
  }
}
vector<pair<int, int>> que[2];
int ptr[2];
inline int pick() {
  return ptr[1] < que[1].size() &&
         (ptr[0] == que[0].size() ||
          que[1][ptr[1]].first < que[0][ptr[0]].first);
}
inline long long solve() {
  que[0].clear();
  que[1].clear();
  ptr[0] = ptr[1] = 0;
  int sum = 0;
  for (int i = link_next[maxn - 1]; i > 0; i = link_next[i]) {
    que[0].emplace_back(i, tot[i]);
    sum += i * tot[i];
  }
  sort(que[0].begin(), que[0].end());
  long long res = 0;
  while (true) {
    int x = pick();
    if (que[x][ptr[x]] == make_pair(sum, 1)) {
      break;
    }
    if (que[x][ptr[x]].second > 1) {
      que[1].emplace_back(que[x][ptr[x]].first * 2, que[x][ptr[x]].second / 2);
      res += (long long)que[x][ptr[x]].first * 2 * (que[x][ptr[x]].second / 2);
      if (que[x][ptr[x]].second % 2) {
        que[x][ptr[x]].second = 1;
      } else {
        ++ptr[x];
      }
    } else {
      int tmpval = que[x][ptr[x]++].first;
      int y = pick();
      que[1].emplace_back(tmpval + que[y][ptr[y]].first, 1);
      res += tmpval + que[y][ptr[y]].first;
      if (--que[y][ptr[y]].second == 0) {
        ++ptr[y];
      }
    }
  }
  return res;
}
int main() {
  int n, q;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", a + i);
  }
  scanf("%d", &q);
  for (int i = 0; i < q; ++i) {
    int l, r;
    scanf("%d%d", &l, &r);
    l--;
    r--;
    queries.emplace_back(l, r, i);
  }
  sort((queries).begin(), (queries).end());
  vector<Query>::iterator query = queries.begin();
  for (int i = 0; i < maxn; i += BLOCK_SIZE) {
    int l = i, r = i - 1;
    memset(link_prev, 0, sizeof link_prev);
    memset(link_next, 0, sizeof link_next);
    while (query != queries.end() && query->l / BLOCK_SIZE * BLOCK_SIZE == i) {
      while (query->r > r) add(++r, 1);
      while (query->l < l) add(--l, 1);
      while (query->l > l) add(l++, -1);
      results[query->id] = solve();
      query++;
    }
    for (int k = l; k <= r; ++k) {
      tot[cnt[a[k]]] = 0;
      cnt[a[k]] = 0;
    }
  }
  for (int i = 0; i < q; ++i) {
    cout << results[i] << endl;
  }
}
