Alice 想向 Bob 发送一条重要消息。消息 a = (a1, ..., an) 是正整数(字符)序列。
为了压缩消息,Alice 想使用二进制霍夫曼编码。我们记得二进制霍夫曼码或二进制前缀码是一个函数 f,它将字符串中出现的每个字母映射到某个二进制字符串(即仅由字符“0”和“1”组成的字符串),这样对于每对不同的字符 ai 和 aj,字符串 f(ai) 不是 f(aj) 的前缀(反之亦然)。消息a1,a2,...,an的编码结果是每个字符的编码串联,即字符串f(a1)f(a2)...f(an)。霍夫曼码非常有用,因为如果给出函数 f,则可以轻松且唯一地解压缩压缩消息。通常选择代码是为了最小化压缩消息的总长度,即字符串 f(a1)f(a2)...f(an) 的长度。
由于安全问题,Alice 不想发送整个消息。相反,她选择了消息的一些子字符串并希望单独发送它们。对于每个给定的子串 ali...ari,她想知道霍夫曼编码的最小可能长度。帮她解决这个问题。
输入
输入的第一行包含单个整数 n (1 ≤ n ≤ 100 000) — 初始消息的长度。第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 100 000) — 消息的字符。
下一行包含单个整数 q (1 ≤ q ≤ 100 000) — 查询数。
然后 q 行后面是查询描述。这些行中的第 i 行包含两个整数 li 和 ri (1 ≤ li ≤ ri ≤ n)——分别是第 i 个子串的左端和右端的位置。位置从 1 开始编号。子串可以以任何方式重叠。相同的子字符串可能在输入中出现多次。
输出
打印 q 行。每行应包含一个整数 - 子字符串 ali...ari 的霍夫曼编码的最小可能长度。
示例
输入 #1
7 1 2 1 3 1 2 1 5 1 7 1 3 3 5 2 4 4 4
输出 #1
10 3 3 5 0
注意
在第一个查询中,对子字符串进行编码的最佳方法之一是将 1 映射到“0”、2 映射到“10”、3 映射到“11”。
请注意,将字母映射到空子字符串是正确的(如示例中的第五个查询所示)。