#include <bits/stdc++.h>
using namespace std;
int n, a[100010], freq[100010], cnt[100010], ans[100010], nodeInd[100010],
    nextInd[2 * 320], prevInd[2 * 320], val[2 * 320];
vector<vector<pair<pair<int, int>, int> > > blocks(320);
queue<int> freeInd;
void CreateNode(int x) {
  int i, j;
  if (nodeInd[x + 1] != 0) {
    j = nodeInd[x + 1];
    i = prevInd[j];
  } else {
    i = nodeInd[x - 1];
    j = nextInd[i];
  }
  int k = freeInd.front();
  freeInd.pop();
  val[k] = x;
  nodeInd[x] = k;
  prevInd[k] = i;
  nextInd[k] = j;
  nextInd[i] = k;
  prevInd[j] = k;
}
void EraseNode(int x) {
  int k = nodeInd[x];
  int j = nextInd[k];
  int i = prevInd[k];
  nextInd[i] = j;
  prevInd[j] = i;
  freeInd.push(k);
  nodeInd[x] = 0;
}
void Increment(int i) {
  freq[i]++;
  i = freq[i];
  cnt[i]++;
  cnt[i - 1]--;
  if (cnt[i] == 1) CreateNode(i);
  if (cnt[i - 1] == 0) EraseNode(i - 1);
}
void Decrement(int i) {
  freq[i]--;
  i = freq[i];
  cnt[i]++;
  cnt[i + 1]--;
  if (cnt[i] == 1) CreateNode(i);
  if (cnt[i + 1] == 0) EraseNode(i + 1);
}
int SingleCountPush(pair<int, int> a, deque<pair<int, int> >& Q1,
                    deque<pair<int, int> >& Q2) {
  pair<int, int> b = Q1.front();
  Q1.pop_front();
  if (--b.second) Q1.push_front(b);
  Q2.push_back(make_pair(a.first + b.first, 1));
  return a.first + b.first;
}
int MultiCountPush(deque<pair<int, int> >& Q1, deque<pair<int, int> >& Q2) {
  pair<int, int> a = Q1.front();
  Q1.pop_front();
  if (a.second % 2) Q1.push_front(make_pair(a.first, 1));
  Q2.push_back(make_pair(a.first + a.first, a.second / 2));
  return (a.first + a.first) * (a.second / 2);
}
int Query() {
  deque<pair<int, int> > Q1, Q2;
  int ans = 0;
  for (int x = nextInd[0]; x != 0; x = nextInd[x])
    Q1.push_back(make_pair(val[x], cnt[val[x]]));
  if (Q1.size() == 1 && Q1.front().second == 1) return 0;
  if (Q1.front().second == 1) {
    pair<int, int> a = Q1.front();
    Q1.pop_front();
    ans += SingleCountPush(a, Q1, Q2);
  } else
    ans += MultiCountPush(Q1, Q2);
  while (!Q1.empty()) {
    if (Q1.front().first <= Q2.front().first) {
      if (Q1.front().second == 1) {
        pair<int, int> a = Q1.front();
        Q1.pop_front();
        if (!Q1.empty() && (Q1.front().first <= Q2.front().first))
          ans += SingleCountPush(a, Q1, Q2);
        else
          ans += SingleCountPush(a, Q2, Q2);
      } else
        ans += MultiCountPush(Q1, Q2);
    } else {
      if (Q2.front().second == 1) {
        pair<int, int> a = Q2.front();
        Q2.pop_front();
        if (!Q2.empty() && (Q2.front().first < Q1.front().first))
          ans += SingleCountPush(a, Q2, Q2);
        else
          ans += SingleCountPush(a, Q1, Q2);
      } else
        ans += MultiCountPush(Q2, Q2);
    }
  }
  while (!(Q2.size() == 1 && Q2.front().second == 1)) {
    if (Q2.front().second == 1) {
      pair<int, int> a = Q2.front();
      Q2.pop_front();
      ans += SingleCountPush(a, Q2, Q2);
    } else
      ans += MultiCountPush(Q2, Q2);
  }
  return ans;
}
void MO(vector<pair<pair<int, int>, int> >& block) {
  if (block.size() == 0) return;
  int i, j, k, x, l, r;
  sort(block.begin(), block.end());
  for (i = 1; i <= 100010; i++) freq[i] = cnt[i] = nodeInd[i] = 0;
  cnt[0] = n + 1;
  while (!freeInd.empty()) freeInd.pop();
  for (i = 0; i < 2 * 320; i++) {
    nextInd[i] = prevInd[i] = 0;
    freeInd.push(i);
  }
  freeInd.pop();
  for (x = 0, i = j = 0; x < block.size(); x++) {
    r = block[x].first.first;
    l = block[x].first.second;
    k = block[x].second;
    if (j != r) {
      if (j < r) {
        for (j++; j <= r; j++) Increment(a[j]);
        j--;
      } else {
        for (; j > r; j--) Decrement(a[j]);
      }
    }
    if (i != l) {
      if (i < l) {
        if (i == 0) i = 1;
        for (; i < l; i++) Decrement(a[i]);
      } else {
        for (i--; i >= l; i--) Increment(a[i]);
        i++;
      }
    }
    ans[k] = Query();
  }
}
int main() {
  int m, q, i, j, k, x, y, z;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%d", &a[i]);
  scanf("%d", &q);
  for (x = 1; x <= q; x++) {
    scanf("%d%d", &i, &j);
    blocks[i / 320].push_back(make_pair(make_pair(j, i), x));
  }
  for (x = 0; x < 320; x++) MO(blocks[x]);
  for (x = 1; x <= q; x++) printf("%d\n", ans[x]);
  return 0;
}
