← 返回题目列表

Codeforces · 700/D

D. 段上的霍夫曼编码

中文机器翻译题面 查看原题

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”。

请注意,将字母映射到空子字符串是正确的(如示例中的第五个查询所示)。