Problem 2. Sleeping in Class

USACO 2022 February Contest, Platinum

奶牛 Bessie 很兴奋最近重返线下上课了！不幸的是，她的讲师 Farmer John 讲课非常无聊，因此她经常在课堂上打瞌睡。

Farmer John 注意到 Bessie 在课堂上没有专心听讲。他让班上的另一名学生 Elsie 记录 Bessie 在一节课中睡着的次数。总共有 $N$ 个课时（$2\le N\le 10^5$），Elsie 记录下 Bessie 在第 $i$ 个课时睡着了 $a_i$ 次（$1\le a_i\le 10^{18}$）。Bessie 在所有课时期间睡着的总次数不超过 $10^{18}$。

Elsie 感觉与 Bessie 竞争非常激烈，从而想让 Farmer John 觉得 Bessie 在每节课上总是睡着相同的次数——让问题看起来完全是 Bessie 的错，而与 Farmer John 有时无聊的讲课无关。

Elsie 可以修改记录的方式只有合并两个相邻的课时或将一个课时拆分为两个。例如，如果 $a=[1,2,3,4,5]$，那么如果 Elsie 合并第二和第三课时则记录将变为 $[1,5,4,5]$。如果 Elsie 接下来将第三个课时拆分为两个，则记录可以变为 $[1,5,0,4,5]$，$[1,5,1,3,5]$，$[1,5,2,2,5]$，$[1,5,3,1,5]$ 和 $[1,5,4,0,5]$ 之一。

给定 $Q$（$1\le Q\le 10^5$）个 Bessie 最不喜欢的数的候选 $q_1,\ldots,q_Q$（$1\le q_i\le 10^{18}$），对其中每个数帮助 Elsie 计算她需要对记录进行的最小修改次数，使得记录中的所有数相等。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 $N$，第二行包含 $a_1,a_2,\ldots,a_N$。第三行包含 $Q$，以下 $Q$ 行每行包含一个整数 $q_i$，为一个 Bessie 最不喜欢的数的候选。

输出格式（输出至终端 / 标准输出）：

对于每一个 $q_i$，输出 Elsie 需要对记录进行的最小修改次数，使得记录中的所有数均变为 $q_i$，如果不可能则输出 $-1$。

输入样例：

6
1 2 3 1 1 4
7
1
2
3
4
5
6
12

输出样例：

6
6
4
5
-1
4
5

Elsie 需要至少四次操作将记录中所有数变为 3。

   1 2 3 1 1 4
-> 3 3 1 1 4
-> 3 3 1 5
-> 3 3 6
-> 3 3 3 3

Elsie 不可能将记录中所有数变为 5，这是这个候选的答案为 $-1$ 的原因。

测试点性质： 测试点 2-4 中，$N,Q\le 5000$。测试点 5-7 中，所有 $a_i$ 不超过 $10^9$。测试点 8-26 没有额外限制。

供题：Jesse Choe，Benjamin Qi