Alice wants to send an important message to Bob. Message a = (a1, ..., an) is a sequence of positive integers (characters).

To compress the message Alice wants to use binary Huffman coding. We recall that binary Huffman code, or binary prefix code is a function f, that maps each letter that appears in the string to some binary string (that is, string consisting of characters '0' and '1' only) such that for each pair of different characters ai and aj string f(ai) is not a prefix of f(aj) (and vice versa). The result of the encoding of the message a1, a2, ..., an is the concatenation of the encoding of each character, that is the string f(a1)f(a2)... f(an). Huffman codes are very useful, as the compressed message can be easily and uniquely decompressed, if the function f is given. Code is usually chosen in order to minimize the total length of the compressed message, i.e. the length of the string f(a1)f(a2)... f(an).

Because of security issues Alice doesn't want to send the whole message. Instead, she picks some substrings of the message and wants to send them separately. For each of the given substrings ali... ari she wants to know the minimum possible length of the Huffman coding. Help her solve this problem.

Input

The first line of the input contains the single integer n (1 ≤ n ≤ 100 000) — the length of the initial message. The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 100 000) — characters of the message.

Next line contains the single integer q (1 ≤ q ≤ 100 000) — the number of queries.

Then follow q lines with queries descriptions. The i-th of these lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n) — the position of the left and right ends of the i-th substring respectively. Positions are numbered from 1. Substrings may overlap in any way. The same substring may appear in the input more than once.

Output

Print q lines. Each line should contain a single integer — the minimum possible length of the Huffman encoding of the substring ali... ari.

Example

Input

7
1 2 1 3 1 2 1
5
1 7
1 3
3 5
2 4
4 4


Output

10
3
3
5
0

Note

In the first query, one of the optimal ways to encode the substring is to map 1 to "0", 2 to "10" and 3 to "11".

Note that it is correct to map the letter to the empty substring (as in the fifth query from the sample).
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Jialin Ouyang (Jialin.Ouyang@gmail.com)
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    QuickScanner in = new QuickScanner(inputStream);
    QuickWriter out = new QuickWriter(outputStream);
    TaskD solver = new TaskD();
    solver.solve(1, in, out);
    out.close();
  }

  static class TaskD {
    static final int MAX = 100000 + 10;
    static final int BLOCK = 317 + 5;
    int n;
    int[] S;
    int m;
    Query[] queries;
    long[] answer;

    public void solve(int testNumber, QuickScanner in, QuickWriter out) {
      n = in.nextInt();
      S = new int[n];
      for (int i = 0; i < n; ++i) {
        S[i] = in.nextInt();
      }
      m = in.nextInt();
      queries = new Query[m];
      answer = new long[m];
      for (int i = 0; i < m; ++i) {
        int l = in.nextInt() - 1;
        int r = in.nextInt();
        queries[i] = new Query(l, r, i);
      }
      Arrays.sort(queries);
      FreqQueue q = new FreqQueue();
      HuffmanCode hc = new HuffmanCode();
      int l = 0, r = 0;
      for (int i = 0; i < m; ++i) {
        Query query = queries[i];
        //System.out.printf("l:%d r:%d\n", query.l, query.r);
        if (i == 0 || queries[i - 1].l / BLOCK != query.l / BLOCK) {
          for (int j = l; j < r; ++j) {
            q.decFreq(S[j]);
          }
          for (int j = query.l; j < query.r; ++j) {
            q.incFreq(S[j]);
          }
          l = query.l;
          r = query.r;
        }
        assert (r <= query.r);
        for (; r < query.r; ++r) q.incFreq(S[r]);
        for (; l < query.l; ++l) q.decFreq(S[l]);
        for (; query.l < l; --l) q.incFreq(S[l - 1]);
        hc.init(q);
        answer[query.idx] = hc.calc();
      }
      out.print(answer, "\n");
    }

    class Query implements Comparable<Query> {
      int l;
      int r;
      int idx;

      public Query(int l, int r, int idx) {
        this.l = l;
        this.r = r;
        this.idx = idx;
      }


      public int compareTo(Query o) {
        return l / BLOCK != o.l / BLOCK ? l - o.l : r - o.r;
      }

    }

    class HuffmanCode {
      IntArrayDeque freq1;
      IntArrayDeque freq2;
      IntArrayDeque freqCnt1;
      IntArrayDeque freqCnt2;

      public HuffmanCode() {
        freq1 = new IntArrayDeque(BLOCK << 1);
        freqCnt1 = new IntArrayDeque(BLOCK << 1);
        freq2 = new IntArrayDeque(BLOCK << 1);
        freqCnt2 = new IntArrayDeque(BLOCK << 1);
      }

      void init(FreqQueue q) {
        freq1.clear();
        freqCnt1.clear();
        freq2.clear();
        freqCnt2.clear();
        //q.print();
        for (int i = q.next[0]; i < MAX - 1; i = q.next[i]) {
          freq1.add(i);
          freqCnt1.add(q.freqCnt[i]);
        }
      }

      long calc() {
        long res = 0;
        while (true) {
          if (!freq1.isEmpty() && !freq2.isEmpty() && freq1.peek() == freq2.peek()) {
            freq1.poll();
            int fc = freqCnt1.poll() + freqCnt2.poll();
            freqCnt2.addFirst(fc);
          }
          //System.out.print("\t\t["); for (int x : freq1) System.out.printf("%d ", x); System.out.println("]");
          //System.out.print("\t\t["); for (int x : freqCnt1) System.out.printf("%d ", x); System.out.println("]");
          //System.out.print("\t\t["); for (int x : freq2) System.out.printf("%d ", x); System.out.println("]");
          //System.out.print("\t\t["); for (int x : freqCnt2) System.out.printf("%d ", x); System.out.println("]");
          int f1;
          if (freq1.isEmpty() || (!freq2.isEmpty() && freq2.peek() < freq1.peek())) {
            if (freqCnt2.peek() > 1) {
              res += simplePoll(freq2, freqCnt2);
              continue;
            } else {
              f1 = freq2.poll();
              freqCnt2.poll();
            }
          } else {
            if (freqCnt1.peek() > 1) {
              res += simplePoll(freq1, freqCnt1);
              continue;
            } else {
              f1 = freq1.poll();
              freqCnt1.poll();
            }
          }
          if (freq1.isEmpty() && freq2.isEmpty()) break;
          int f2;
          if (freq1.isEmpty() || (!freq2.isEmpty() && freq2.peek() < freq1.peek())) {
            f2 = freq2.peek();
            poll(freq2, freqCnt2);
          } else {
            f2 = freq1.peek();
            poll(freq1, freqCnt1);
          }
          res += f1 + f2;
          freq2.add(f1 + f2);
          freqCnt2.add(1);
        }
        return res;
      }

      long simplePoll(IntArrayDeque freq, IntArrayDeque freqCnt) {
        int f = freq.poll();
        int fc = freqCnt.poll();
        freq2.add(f << 1);
        freqCnt2.add(fc >> 1);
        if ((fc & 1) == 1) {
          freq.addFirst(f);
          freqCnt.addFirst(1);
        }
        return (long) f * (fc >> 1 << 1);
      }

      void poll(IntArrayDeque freq, IntArrayDeque freqCnt) {
        int cnt = freqCnt.poll();
        if (cnt > 1) {
          freqCnt.addFirst(cnt - 1);
        } else {
          freq.poll();
        }
      }

    }

    class FreqQueue {
      int[] next;
      int[] prev;
      int[] freq;
      int[] freqCnt;

      public FreqQueue() {
        next = new int[MAX];
        prev = new int[MAX];
        freq = new int[MAX];
        freqCnt = new int[MAX];
        next[0] = MAX - 1;
        prev[0] = 0;
        next[MAX - 1] = MAX - 1;
        prev[MAX - 1] = 0;
        freqCnt[0] = MAX;
      }

      public void incFreq(int idx) {
        int freq = this.freq[idx];
        ++this.freq[idx];
        --freqCnt[freq];
        ++freqCnt[freq + 1];
        if (freqCnt[freq + 1] == 1) {
          addPoint(freq + 1, freq, next[freq]);
        }
        if (freqCnt[freq] == 0) {
          removePoint(freq);
        }
      }

      public void decFreq(int idx) {
        int freq = this.freq[idx];
        --this.freq[idx];
        --freqCnt[freq];
        ++freqCnt[freq - 1];
        if (freqCnt[freq - 1] == 1) {
          addPoint(freq - 1, prev[freq], freq);
        }
        if (freqCnt[freq] == 0) {
          removePoint(freq);
        }
      }

      private void addPoint(int currP, int prevP, int nextP) {
        next[currP] = next[prevP];
        next[prevP] = currP;
        prev[nextP] = currP;
        prev[currP] = prevP;
      }

      private void removePoint(int currP) {
        next[prev[currP]] = next[currP];
        prev[next[currP]] = prev[currP];
      }

    }

    class IntArrayDeque extends IntArrayQueue {
      public IntArrayDeque(int capacity) {
        super(capacity);
      }

      public void addFirst(int v) {
        ensureCapacity(size() + 1);
        open = (open - 1) & (data.length - 1);
        data[open] = v;
      }

    }

    class IntArrayQueue implements TaskD.IntCollection {
      protected int[] data;
      protected int open;
      protected int close;

      public IntArrayQueue(int capacity) {
        data = new int[Integer.highestOneBit(capacity) << 1];
      }

      public void clear() {
        open = close = 0;
      }


      public int size() {
        return (close - open) & (data.length - 1);
      }


      public void add(int v) {
        ensureCapacity(size() + 1);
        data[close++] = v;
        close &= data.length - 1;
      }

      public int peek() {
        assert (open != close);
        return data[open];
      }

      public int poll() {
        assert (open != close);
        int res = data[open];
        open = (open + 1) & (data.length - 1);
        return res;
      }

      protected void ensureCapacity(int capacity) {
        if (capacity < data.length) return;
        int[] newData = new int[Integer.highestOneBit(capacity) << 1];
        for (int i = 0, j = open; j != close; i++, j = (j + 1) & (data.length - 1)) {
          newData[i] = data[j];
        }
        close = size();
        open = 0;
        data = newData;
      }

    }

    interface IntCollection {
      int size();

      default boolean isEmpty() {
        return size() == 0;
      }

    }

  }

  static class QuickWriter {
    private final PrintWriter writer;

    public QuickWriter(OutputStream outputStream) {
      this.writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public QuickWriter(Writer writer) {
      this.writer = new PrintWriter(writer);
    }

    public void print(long[] objects, String delimiter) {
      for (int i = 0; i < objects.length; ++i) {
        if (i > 0) {
          writer.print(delimiter);
        }
        writer.print(objects[i]);
      }
    }

    public void close() {
      writer.close();
    }

  }

  static class QuickScanner {
    private static final int BUFFER_SIZE = 1024;
    private InputStream stream;
    private byte[] buffer;
    private int currentPostion;
    private int numberOfChars;

    public QuickScanner(InputStream stream) {
      this.stream = stream;
      this.buffer = new byte[BUFFER_SIZE];
      this.currentPostion = 0;
      this.numberOfChars = 0;
    }

    public int nextInt() {
      int c = nextNonSpaceChar();
      boolean positive = true;
      if (c == '-') {
        positive = false;
        c = nextChar();
      }
      int res = 0;
      do {
        if (c < '0' || '9' < c) {
          throw new RuntimeException();
        }
        res = res * 10 + c - '0';
        c = nextChar();
      } while (!isSpaceChar(c));
      return positive ? res : -res;
    }

    public int nextNonSpaceChar() {
      int res = nextChar();
      for (; isSpaceChar(res) || res < 0; res = nextChar()) ;
      return res;
    }

    public int nextChar() {
      if (numberOfChars == -1) {
        throw new RuntimeException();
      }
      if (currentPostion >= numberOfChars) {
        currentPostion = 0;
        try {
          numberOfChars = stream.read(buffer);
        } catch (Exception e) {
          throw new RuntimeException(e);
        }
        if (numberOfChars <= 0) {
          return -1;
        }
      }
      return buffer[currentPostion++];
    }

    public boolean isSpaceChar(int c) {
      return c == ' '
          || c == '\n'
          || c == '\r'
          || c == '\t'
          || c < 0;
    }

  }
}

