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.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class D {
	static PrintWriter out = new PrintWriter(System.out);

	static final int MAX = 1_000_01, SQRT = 500;

	
	static int N,Q;
	static int[] ar;
	static long[] answers;
	static Query qs[];
	
	static HashSet<Integer> geqRoot;
	static int[] myFreq, atFreq;
	
	static final boolean debug = false; 
	
	public static void main(String[] args) {
		FS in = new FS();
		N = in.nextInt();
		ar = new int[N];
		for(int i = 0; i < N; i++) ar[i] = in.nextInt()-1;
		Q = in.nextInt();
		qs = new Query[Q];
		answers = new long[Q];

		for(int i = 0; i < Q; i++) {
			int l = in.nextInt()-1;
			int r = in.nextInt()-1;
			qs[i] = new Query(l,r,i);
			if(l == r) answers[i] = 0;
		}
		Arrays.sort(qs);
		
		int l = 0, r = -1;
		myFreq = new int[MAX];
		atFreq = new int[SQRT];
		geqRoot = new HashSet<Integer>();
		atFreq[0] = N; // doesn't matter
		
		for(int qq = 0; qq < Q; qq++) {
			Query q = qs[qq];
			if(q.l == q.r) continue;
			// expand right ptr
			while(r < q.r) add(ar[++r]);
			//expand left ptr
			while(l > q.l) add(ar[--l]);
			//remove right ptr
			while(r > q.r) rem(ar[r--]);
			//remove left ptr
			while(l < q.l) rem(ar[l++]);
			
			// Now solve 
			long res = 0;
			
			PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
			for(int ii : geqRoot) pq.add(myFreq[ii]);
			
			// solve everything of size < root
			
			int curFreq[] = Arrays.copyOf(atFreq, atFreq.length);
			
			int leftover = -1;
			for(int i = 1; i < SQRT; i++) {
				int here = curFreq[i];
				if(here == 0) continue;

				if(leftover != -1) {
					//pair with him
					int newval = leftover+i;
					res += newval;
					
					if(newval >= SQRT) pq.add(newval);
					else curFreq[newval]++;
					
					leftover = -1;
					here--;
				}
				if((here&1) == 1) {
					// will have leftover
					leftover = i;
					here--;
				}

				res += ((long)(i))*here;
				int newval = i*2;
				if(newval >= SQRT) {
					for(int j = 0; j < here>>1; j++) pq.add(newval);
				}
				else {
					curFreq[newval] += here>>1;
				}
			}
			if(leftover != -1) pq.add(leftover);
			
			while(pq.size() > 1) {
				int a = pq.poll();
				int b = pq.poll();
				res += (a+b);
				pq.add(a+b);
			}
			answers[q.id] = res;
		}
		
		for(int i = 0; i < Q; i++) out.println(answers[i]);
		out.close();
	}
	
	static void add(int val) {
		if(myFreq[val] >= SQRT) {
			myFreq[val]++;
		}
		else if(myFreq[val] == SQRT-1) {
			atFreq[SQRT-1]--;
			myFreq[val]++;
			geqRoot.add(val);
		}
		else {
			atFreq[myFreq[val]]--;
			myFreq[val]++;
			atFreq[myFreq[val]]++;
		}
	}
	static void rem(int val) {
		if(myFreq[val] < SQRT) {
			atFreq[myFreq[val]]--;
			myFreq[val]--;
			atFreq[myFreq[val]]++;
		}
		else if(myFreq[val] == SQRT) {
			geqRoot.remove(val);
			atFreq[SQRT-1]++;
			myFreq[val]--;
		}
		else {
			myFreq[val]--;
		}
	}
	
	static class Query implements Comparable<Query>{
		int l, r, id, buck;
		public Query(int ll, int rr, int ii) {
			l=ll;
			r=rr;
			id=ii;
			buck = l/SQRT;
		}
		@Override
		public int compareTo(Query o) {
			if(buck != o.buck) return buck-o.buck;
			return r-o.r;
		}
	}
	
	static class FS{
		BufferedReader br;
		StringTokenizer st;
		public FS() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {st = new StringTokenizer(br.readLine());}
				catch(Exception e) { throw null;}
			}
			return st.nextToken();
		}
		int nextInt() { return Integer.parseInt(next());}
		double nextDouble() { return Double.parseDouble(next());}
		long nextLong() { return Long.parseLong(next());}
		int[] NIA(int n) {
			int r[] = new int[n];
			for(int i = 0; i < n; i++) r[i] = nextInt();
			return r;
		}
		long[] NLA(int n) {
			long r[] = new long[n];
			for(int i = 0; i < n; i++) r[i] = nextLong();
			return r;
		}
		char[][] grid(int r, int c){
			char res[][] = new char[r][c];
			for(int i = 0; i < r; i++) {
				char l[] = next().toCharArray();
				for(int j = 0; j < c; j++) {
					res[i][j] = l[j];
				}
			}
			return res;
		}
	}
	
}
