Bakery

题意翻译

$\texttt{Monocrap}$ 希望在当地开一间面包店。但是首先他要研究研究他的面包店能否在激烈的市场竞争中生存下来。 $\texttt{Monocrap}$ 计划开这座面包店开 $n$ 天。在第 $i$ 天，$a_i$ 块面包会在开店之前烤出。在最后一天，$\texttt{Monocrap}$ 会通过大降价的方式卖出所有库存的面包。 $\texttt{Monocrap}$ 的销售方案是这样的：首先，他会销售今天所烤的面包；然后他会销售昨天没卖出去的面包；然后是两天前没卖出去的面包，以此类推。 因为有些顾客可能会买到面包店里放了很多天的面包，所以他们会传播负面评价。我们定义一块面包的“难吃值”为它销售日期到生产日期之间的天数，进一步定义这 $n$ 天的“口碑损失值” 为所有卖出去的面包“难吃值”最大值。 假设每天都会有正好 $k$ 位顾客来买 $\texttt{Monocrap}$ 面包店的面包，每位顾客正好会买一块面包，但如果没面包了就什么都不买。特别的，如前文所说，最后一天时所有面包都会被卖出，且仍计入“口碑损失值”。 现在 $\texttt{Monocrap}$ 已经规划好了 $n$ 天的烤面包数 $a_1,a_2,...,a_n$，不过他还有 $m$ 次询问，每次给定顾客数 $k$ ，求此时面包店的“口碑损失值”。 $1\leq n,m\leq 2\times10^5.$ $1\leq a_i\leq 10^9,1\leq k_1<k_2<...<k_m\leq10^9.$

题目描述

Monocarp would like to open a bakery in his local area. But, at first, he should figure out whether he can compete with other shops. Monocarp plans that the bakery will work for $ n $ days. On the $ i $ -th day, $ a_i $ loaves of bread will be baked in the morning before the opening. At the end of the $ n $ -th day, Monocarp will sell all the remaining bread that wasn't sold earlier with a huge discount. Because of how bread is stored, the bakery seller sells the bread in the following order: firstly, he sells the loaves that were baked that morning; secondly, he sells the loaves that were baked the day before and weren't sold yet; then the loaves that were baked two days before and weren't sold yet, and so on. That's why some customers may buy a rather stale bread and will definitely spread negative rumors. Let's define loaf spoilage as the difference between the day it was baked and the day it was sold. Then the unattractiveness of the bakery will be equal to the maximum spoilage among all loaves of bread baked at the bakery. Suppose Monocarp's local area has consumer demand equal to $ k $ , it means that each day $ k $ customers will come to the bakery and each of them will ask for one loaf of bread (the loaves are sold according to the aforementioned order). If there is no bread left, then the person just doesn't buy anything. During the last day sale, all the remaining loaves will be sold (and they will still count in the calculation of the unattractiveness). Monocarp analyzed his competitors' data and came up with $ m $ possible consumer demand values $ k_1, k_2, \dots, k_m $ , and now he'd like to calculate the unattractiveness of the bakery for each value of demand. Can you help him?

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1 \le n \le 2 \cdot 10^5 $ ; $ 1 \le m \le 2 \cdot 10^5 $ ) — the number of days the bakery is open and the number of possible values of consumer demand. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the number of bread loaves that will be baked each day. The third line contains $ m $ integers $ k_1, k_2, \dots, k_m $ ( $ 1 \le k_1 < k_2 < \dots < k_m \le 10^9 $ ) — the possible consumer demand values in the ascending order.

输出格式

Print $ m $ integers: for each consumer demand, print the unattractiveness of the bakery.

输入输出样例

输入样例 #1

5 4
5 2 1 3 7
1 3 4 10

输出样例 #1

4 2 1 0

输入样例 #2

8 9
3 1 4 1 5 9 2 6
1 2 3 4 5 6 7 8 9

输出样例 #2

7 5 3 3 2 1 1 1 0

说明

In the first example, let's describe what happens for couple consumer demands: If consumer demand is equal to $ 1 $ : - at day $ 1 $ : $ 5 $ loaves are baked and only $ 1 $ is sold with spoilage equal to $ 1 - 1 = 0 $ ; - at day $ 2 $ : $ 4 $ loaves are left and $ 2 $ more are baked. Only $ 1 $ loaf was sold and it was the loaf baked today with spoilage $ 2 - 2 = 0 $ ; - at day $ 3 $ : $ 4 $ loaves from the first day and $ 1 $ loaf from the second day left. One more loaf was baked and was sold this day with spoilage $ 3 - 3 = 0 $ ; - at day $ 4 $ : $ 4 $ loaves from the first day and $ 1 $ loaf from the second day left. $ 3 $ more loaves were baked and one of them was sold this day with spoilage $ 4 - 4 = 0 $ ; - at day $ 5 $ : $ 4 $ loaves from the first day, $ 1 $ loaf from the second day and $ 2 $ loaves from the fourth day left. $ 7 $ more loaves were baked and, since it's the last day, all $ 14 $ loaves were sold. $ 4 $ loaves from the first day have the maximum spoilage equal to $ 5 - 1 = 4 $ . In total, the unattractiveness of the bakery will be equal to $ 4 $ .If consumer demand is equal to $ 10 $ then all baked bread will be sold in the day it was baked and will have spoilage equal to $ 0 $ .