题目描述

最近终于线下授课了，奶牛 Bessie 十分兴奋！不幸的是，小理是一个非常无聊的讲师，因此她经常课堂上睡觉。

小理注意到了 Bessie 上课走神。他要求班上的另一个学生 Elsie 跟踪记录给定课上 Bessie 睡觉的次数。一共有 $N$ 堂课，Elsie 记录下了 Bessie 在第 $i$ 堂课睡了 $a_i$ 次。所有课上 Bessie 一共睡觉的次数最多为 $10^{18}$。

Elsie 认为自己是 Bessie 的竞争对手，所以她想让小理觉得在每堂课上 Bessie 都一直睡了同样多次——让小理觉得这个问题显然完全是 Bessie 的错，而不是小理有时上课很无聊的问题。

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$ 个候选的 Bessie 最不喜欢的数字 $q_1,\ldots,q_Q$，对于每个数字，请帮助 Elsie 计算她至少要操作多少次，才能让记录里的所有数字都变成这个数字。

输入格式

输入共 $Q+3$ 行。

第一行一个整数 $N$。

第二行 $N$ 个整数 $a_1,a_2,\ldots, a_N$。

第三行一个整数 $Q$。

接下来 $Q$ 行，每行一个整数 $q_i$，表示 Bessie 最不喜欢的数字。

输出格式

对于每个 $q_i$，计算 Elsie 把记录里的每个数都变成 $q_i$ 所需要的最小操作次数。如果不能把所有数都变成 $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

数据范围

对于 $100%$ 的数据，保证 $2\le N\le 10^5,1\le a_i\le 10^{18},1\le Q\le 10^5,1\le q_i\le 10^{18}$ 。

• 对于第 $2\sim 4$ 组数据，$N,Q\le 5000$。

• 对于第 $5\sim 7$ 组数据，所有 $a_i$ 最多为 $10^9$。

• 对于第 $8\sim 26$ 组数据，无附加限制。

样例解释

Elsie 需要至少 $4$ 次修改才能让记录里的所有数都变成 $3$。

$$ \begin{aligned} &\ 1\ 2\ 3\ 1\ 1\ 4\ \rightarrow&\ 3\ 3\ 1\ 1\ 4\ \rightarrow&\ 3\ 3\ 1\ 5\ \rightarrow&\ 3\ 3\ 6\ \rightarrow&\ 3\ 3\ 3\ 3\ \end{aligned} $$

Elsie 不可能把记录中的所有数都变成 $5$，因此输出 $-1$。这是正确的。