优化通过网络传输的数据量是开发任何网络应用程序的一个重要且有趣的部分。
在 ZeptoLab 公司深处开发的一款秘密游戏中,游戏宇宙由 n 个级别组成,位于一个圆圈中。您可以从级别 i 到达级别 i - 1 和 i + 1,也可以从级别 1 到达级别 n,反之亦然。第i层描述大小的映射为ai字节。
为了减少传输流量,游戏的等级如下。服务器上的所有关卡都分为 m 组,每次玩家第一次发现自己处于某个组的其中一个关卡时,服务器就会将该组的所有关卡作为单个数据包发送到游戏客户端。因此,当玩家在单个组的关卡内移动时,应用程序不需要任何新信息。由于技术限制,数据包可以包含任意数量的级别,但它们的总大小不得超过 b 字节,其中 b 是某个正整数常量。
通常的情况是玩家一个接一个地完成关卡,这就是为什么决定将 n 个关卡分成 m 组,以便每个组都是包含多个相邻关卡的连续片段(而且,该组可以有两个相邻关卡,n 和 1)。具体地,如果各级描述的总权重最多为b字节,则可以将它们全部合并为一组以单个数据包发送。
确定,为了在遵守上述条件的情况下组织游戏的级别,您需要进行最少多少组?
由于开发游戏是一个漫长的过程,并且技术永远不会停滞,因此尚无法准确预测当游戏结束时限制数据包大小的恒定值将是什么值。这就是为什么开发人员要求您找到 b 的多个值的答案。
输入
第一行包含两个整数 n、q (2 ≤ n ≤ 106, 1 ≤ q ≤ 50) — 游戏宇宙中的关卡数以及需要处理的 b 不同值的数量。
第二行包含 n 个整数 ai (1 ≤ ai ≤ 109) — 级别的大小(以字节为单位)。
接下来的 q 行包含整数 bj ($$\max \{a_{i}\} \leq b_{j} \leq 10^{15}$$),确定常数 b 的值,您需要为此确定答案。
输出
对于来自单行整数 mj (1 ≤ mj ≤ n) 上的输入打印的 kj 的每个值,确定将游戏级别划分为通过网络传输的最小组数,观察给定的条件。
示例
输入 #1
6 3 2 4 2 1 3 2 7 4 6
输出 #1
2 4 3
注意
在测试语句中您可以按以下方式进行。
- 在b = 7处,你可以分为两段:2|421|32(注意其中一个段包含第五、第六和第一级);
- 在 b = 4 处,你可以分为四段:2|4|21|3|2;
- 在 b = 6 处,您可以分为三段:24|21|32|。