题目描述

题目译自 USACO 2022 February Contest, Platinum Problem 2. Sleeping in Class

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

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

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

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 计算她至少要操作多少次，才能让记录里的所有数字都变成这个数字。

输入格式

第一行一个整数 $N\ (2\le N\le 10^5)$。

第二行 $N$ 个整数 $a_1,a_2,\ldots, a_N\ (1\le a_i\le 10^{18})$。

第三行一个整数 $Q\ (1\le Q\le 10^5)$。

接下来 $Q$ 行，每行一个整数 $q_i\ (1\le q_i\le 10^{18})$，表示 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

数据范围与提示

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

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

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