#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
constexpr int kN = int(1E5 + 10);
constexpr int kBlk = 320;
template <typename T>
T ABS(T n) {
  return n >= 0 ? n : -n;
}
static inline char Get_Raw_Char() {
  static char buf[1 << 16], *p = buf, *end = buf;
  if (p == end) {
    if ((end = buf + fread(buf, 1, 1 << 16, stdin)) == buf) return '\0';
    p = buf;
  }
  return *p++;
}
static inline int Get_Digit() {
  char c = Get_Raw_Char();
  while (!isdigit(c)) c = Get_Raw_Char();
  return int(c - '0');
}
static inline int Get_PInt() {
  char c = Get_Raw_Char();
  int ret;
  while (!isdigit(c)) c = Get_Raw_Char();
  ret = int(c - '0');
  while (isdigit(c = Get_Raw_Char())) ret = ret * 10 + int(c - '0');
  return ret;
}
static inline int Get_Int() {
  char c = Get_Raw_Char();
  bool neg = false;
  int ret;
  while (!isdigit(c)) {
    if (c == '-') neg = true;
    c = Get_Raw_Char();
  }
  ret = int(c - '0');
  while (isdigit(c = Get_Raw_Char())) ret = ret * 10 + int(c - '0');
  if (neg) return -ret;
  return ret;
}
static inline long long int Get_ll() {
  char c = Get_Raw_Char();
  bool neg = false;
  long long int ret;
  while (!isdigit(c)) {
    if (c == '-') neg = true;
    c = Get_Raw_Char();
  }
  ret = int(c - '0');
  while (isdigit(c = Get_Raw_Char())) ret = ret * 10 + int(c - '0');
  if (neg) return -ret;
  return ret;
}
static inline long long int Get_Pll() {
  char c = Get_Raw_Char();
  long long int ret;
  while (!isdigit(c)) c = Get_Raw_Char();
  ret = int(c - '0');
  while (isdigit(c = Get_Raw_Char())) ret = ret * 10 + int(c - '0');
  return ret;
}
template <typename T>
static inline void Read_P(T &n) {
  static_assert(is_integral<T>::value);
  char c = Get_Raw_Char();
  while (!isdigit(c)) c = Get_Raw_Char();
  n = int(c - '0');
  while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');
  return;
}
template <typename T>
static inline void Read(T &n) {
  static_assert(is_integral<T>::value);
  char c = Get_Raw_Char();
  bool neg = false;
  while (!isdigit(c)) {
    if (c == '-') neg = true;
    c = Get_Raw_Char();
  }
  n = int(c - '0');
  while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');
  if (neg) n = -n;
  return;
}
template <typename T>
static inline void Read_Digit(T &n) {
  static_assert(is_integral<T>::value);
  char c = Get_Raw_Char();
  while (!isdigit(c)) c = Get_Raw_Char();
  n = int(c - '0');
  return;
}
template <typename T, typename... Targs>
static inline void Read(T &n, Targs &...Fargs) {
  Read(n);
  return Read(Fargs...);
}
template <typename T, typename... Targs>
static inline void Read_Digit(T &n, Targs &...Fargs) {
  Read_Digit(n);
  return Read_Digit(Fargs...);
}
template <typename T, typename... Targs>
static inline void Read_P(T &n, Targs &...Fargs) {
  Read_P(n);
  return Read_P(Fargs...);
}
int a[kN], occ[kN], ans[kN], ql[kN], qr[kN], occcnt[kBlk], xocccnt[kBlk];
set<int> se;
vector<pair<int, int>> query[kBlk];
inline void Insert(int val) {
  if (occ[val] >= kBlk) {
    occ[val]++;
    return;
  } else
    xocccnt[occ[val]++]--;
  if (occ[val] >= kBlk)
    se.insert(val);
  else
    xocccnt[occ[val]]++;
  return;
}
inline void Erase(int val) {
  if (occ[val] >= kBlk) {
    if (--occ[val] >= kBlk)
      return;
    else {
      se.erase(val);
      xocccnt[occ[val]]++;
    }
  } else {
    xocccnt[occ[val]--]--;
    xocccnt[occ[val]]++;
  }
  return;
}
int cal() {
  int ret = 0;
  priority_queue<int, vector<int>, greater<int>> pq;
  for (int i : se) pq.push(occ[i]);
  memcpy(occcnt, xocccnt, sizeof(xocccnt));
  int lst = 0;
  for (int i = 1; i < kBlk; i++)
    if (occcnt[i]) {
      if (lst) {
        ret += i + lst;
        if (i + lst < kBlk)
          occcnt[i + lst]++;
        else
          pq.push(i + lst);
        lst = 0;
        occcnt[i]--;
      }
      if (occcnt[i] & 1) lst = i;
      occcnt[i] >>= 1;
      ret += occcnt[i] * (i << 1);
      if ((i << 1) < kBlk)
        occcnt[i << 1] += occcnt[i];
      else
        for (int j = 1; j <= occcnt[i]; j++) pq.push(i << 1);
    }
  if (lst) pq.push(lst);
  while (pq.size() > 1) {
    int tmp = pq.top();
    pq.pop();
    tmp += pq.top();
    pq.pop();
    ret += tmp;
    pq.push(tmp);
  }
  return ret;
}
int main() {
  int n, q;
  Read_P(n);
  for (int i = 1; i <= n; i++) Read_P(a[i]);
  Read_P(q);
  for (int i = 1; i <= q; i++) Read_P(ql[i], qr[i]);
  for (int i = 1; i <= q; i++)
    query[ql[i] / kBlk].push_back(make_pair(qr[i], i));
  for (int i = 0; i < kBlk; i++)
    if (!query[i].empty()) {
      memset(occ, 0, sizeof(occ));
      memset(xocccnt, 0, sizeof(xocccnt));
      se.clear();
      sort(query[i].begin(), query[i].end());
      int nl = ql[query[i][0].second];
      int nr = nl - 1;
      for (pair<int, int> j : query[i]) {
        while (nr < j.first) Insert(a[++nr]);
        while (nl > ql[j.second]) Insert(a[--nl]);
        while (nl < ql[j.second]) Erase(a[nl++]);
        ans[j.second] = cal();
      }
    }
  for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
}
