CF700D.Huffman Coding on Segment

Alice wants to send an important message to Bob. Message a = (_a_1, ..., a__n) 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 a__i and a__j string f(a__i) is not a prefix of f(a__j) (and vice versa). The result of the encoding of the message _a_1, _a_2, ..., a__n is the concatenation of the encoding of each character, that is the string f(_a_1)f(_a_2)... f(a__n). 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(_a_1)f(_a_2)... f(a__n).

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 a__l__i... a__r__i she wants to know the minimum possible length of the Huffman coding. Help her solve this problem.

爱丽丝想要向鲍勃发送一条重要消息。消息 $a = (a_1, \dots, a_n)$ 是一个正整数（即字符）序列。

为了压缩该消息，爱丽丝希望使用二进制霍夫曼编码（binary Huffman coding）。我们回顾一下：二进制霍夫曼码，或称二进制前缀码（binary prefix code），是一个函数 $f$，它将字符串中出现的每个字符映射到某个二进制字符串（即仅由字符 '0' 和 '1' 组成的字符串），使得对任意两个不同的字符 $a_i$ 和 $a_j$，字符串 $f(a_i)$ 都不是 $f(a_j)$ 的前缀（反之亦然）。消息 $a_1, a_2, \dots, a_n$ 的编码结果是各字符编码的拼接，即字符串 $f(a_1)f(a_2)\dots f(a_n)$。霍夫曼编码非常有用，因为只要给定函数 $f$，压缩后的消息便可轻松且唯一地解压缩。通常，编码的选择目标是最小化压缩后消息的总长度，即字符串 $f(a_1)f(a_2)\dots f(a_n)$ 的长度。

由于安全原因，爱丽丝不希望发送整条消息。相反，她选取消息的一些子串，并希望分别发送这些子串。对于每个给定的子串 $a_{l_i} \dots a_{r_i}$，她想知道其霍夫曼编码的最小可能长度。请帮助她解决该问题。

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 _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 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 l__i and r__i (1 ≤ l__i ≤ r__i ≤ 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.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 100\,000$）—— 初始消息的长度。
第二行包含 $n$ 个整数 $a_1,\,a_2,\,\dots,\,a_n$（$1 \leq a_i \leq 100\,000$）—— 消息的字符。

接下来一行包含一个整数 $q$（$1 \leq q \leq 100\,000$）—— 查询的数量。

随后是 $q$ 行，每行描述一个查询。其中第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq n$）—— 分别表示第 $i$ 个子串的左端点和右端点位置。位置编号从 1 开始。子串可以以任意方式重叠。同一子串可能在输入中多次出现。

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

输出 q 行。每行应包含一个整数——子串 a__l__i... a__r__i 的哈夫曼编码的最小可能长度。

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).

在第一次查询中，对子字符串进行编码的一种最优方式是将 1 映射为 "0"，2 映射为 "10"，3 映射为 "11"。

注意：将字母映射为空子串是合法的（如样例中的第五次查询所示）。