奶牛 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$。
样例
样例输入 1
6
1 2 3 1 1 4
7
1
2
3
4
5
6
12样例输出 1
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 3Elsie 不可能将记录全部变为 5，这就是为什么该候选值的正确输出为 $-1$。
子任务
- 在测试点 2-4 中，$N,Q\le 5000$。
- 在测试点 5-7 中，所有 $a_i$ 最多为 $10^9$。
- 测试点 8-26 满足没有额外限制。
题目来源：Jesse Choe 和 Benjamin Qi