CF526E.Transmitting Levels

Optimizing the amount of data transmitted via a network is an important and interesting part of developing any network application.

In one secret game developed deep in the ZeptoLab company, the game universe consists of n levels, located in a circle. You can get from level i to levels i - 1 and i + 1, also you can get from level 1 to level n and vice versa. The map of the i-th level description size is a__i bytes.

In order to reduce the transmitted traffic, the game gets levels as follows. All the levels on the server are divided into m groups and each time a player finds himself on one of the levels of a certain group for the first time, the server sends all levels of the group to the game client as a single packet. Thus, when a player travels inside the levels of a single group, the application doesn't need any new information. Due to the technical limitations the packet can contain an arbitrary number of levels but their total size mustn't exceed b bytes, where b is some positive integer constant.

Usual situation is that players finish levels one by one, that's why a decision was made to split n levels into m groups so that each group was a continuous segment containing multiple neighboring levels (also, the group can have two adjacent levels, n and 1). Specifically, if the descriptions of all levels have the total weight of at most b bytes, then they can all be united into one group to be sent in a single packet.

Determine, what minimum number of groups do you need to make in order to organize the levels of the game observing the conditions above?

As developing a game is a long process and technology never stagnates, it is yet impossible to predict exactly what value will take constant value b limiting the packet size when the game is out. That's why the developers ask you to find the answer for multiple values of b.

优化通过网络传输的数据量是开发任何网络应用时一项重要且有趣的工作。

在 ZeptoLab 公司内部开发的一款秘密游戏中，游戏宇宙由位于一个环形结构中的 $n$ 个关卡组成。玩家可以从第 $i$ 关前往第 $i-1$ 关和第 $i+1$ 关；此外，也可从第 $1$ 关前往第 $n$ 关，反之亦然。第 $i$ 关的描述数据大小为 $a_i$ 字节。

为减少传输流量，游戏采用如下方式获取关卡数据：服务器将全部 $n$ 个关卡划分为 $m$ 个组；每当玩家首次抵达某个组内的任一关卡时，服务器便将该组内所有关卡的数据作为一个数据包整体发送至客户端。因此，当玩家在某一组内的关卡之间移动时，应用程序无需再请求任何新信息。受技术限制，每个数据包可包含任意数量的关卡，但其总大小不得超过 $b$ 字节，其中 $b$ 是某个给定的正整数常量。

通常情况下，玩家按顺序逐个通关，因此决定将 $n$ 个关卡划分为 $m$ 个组，使得每个组均为一段连续的关卡区间（注意：由于关卡呈环形排列，该“连续”允许包含相邻的第 $n$ 关与第 $1$ 关）。特别地，若某段连续关卡的描述数据总大小不超过 $b$ 字节，则它们可被合并为一个组，并以单个数据包发送。

请确定：在满足上述条件的前提下，最少需要划分成多少个组？

由于游戏开发周期漫长，且技术持续演进，目前尚无法准确预知游戏上线时用于限制数据包大小的常量 $b$ 的具体取值。因此，开发者要求你针对多个不同的 $b$ 值，分别求出对应的答案。

The first line contains two integers n, q (2 ≤ n ≤ 106, 1 ≤ q ≤ 50) — the number of levels in the game universe and the number of distinct values of b that you need to process.

The second line contains n integers a__i (1 ≤ a__i ≤ 109) — the sizes of the levels in bytes.

The next q lines contain integers b__j (), determining the values of constant b, for which you need to determine the answer.

第一行包含两个整数 $n$、$q$（$2 \leq n \leq 10^6$，$1 \leq q \leq 50$）—— 分别表示游戏宇宙中的关卡数量，以及你需要处理的不同 $b$ 值的个数。

第二行包含 $n$ 个整数 $a_i$（$1 \leq a_i \leq 10^9$）—— 表示各关卡的大小（单位：字节）。

接下来的 $q$ 行每行包含一个整数 $b_j$（），用于确定常数 $b$ 的取值，对每个 $b_j$ 需计算并输出对应的答案。

For each value of k__j from the input print on a single line integer m__j (1 ≤ m__j ≤ n), determining the minimum number of groups to divide game levels into for transmission via network observing the given conditions.

对于输入中的每个 $k_j$ 值，在单独一行输出整数 $m_j$（$1 ≤ m_j ≤ n$），表示在满足给定条件的前提下，将游戏关卡划分为网络传输所需的最少组数。

In the test from the statement you can do in the following manner.

• at b = 7 you can divide into two segments: 2|421|32 (note that one of the segments contains the fifth, sixth and first levels);
• at b = 4 you can divide into four segments: 2|4|21|3|2;
• at b = 6 you can divide into three segments: 24|21|32|.

在题目描述的测试用例中，你可以按以下方式操作：

• 当 b = 7 时，可划分为两个段：2|421|32（注意其中一个段包含第五、第六和第一层）；
• 当 b = 4 时，可划分为四个段：2|4|21|3|2；
• 当 b = 6 时，可划分为三个段：24|21|32|。