CF1468B Bakery

Monocarp 想在他所在的地区开一家面包店。但首先，他需要弄清楚自己是否能够与其他商店竞争。 Monocarp 计划让面包店营业 $n$ 天。在第 $i$ 天早上开店前，会烤好 $a_i$ 个面包。在第 $n$ 天结束时，Monocarp 会以超低折扣卖掉所有之前未卖出的剩余面包。 由于面包的储存方式，面包店的售卖顺序如下：首先卖当天早上烤的面包；其次卖前一天剩下的面包；然后卖前两天剩下的面包，依此类推。因此，有些顾客可能会买到相当不新鲜的面包，并且一定会传播负面评价。 我们定义面包的“变质度”为其被烤制的日期与被售出的日期之差。那么，面包店的“吸引力差”就等于所有售出面包中最大变质度。 假设 Monocarp 所在地区的每日顾客需求为 $k$，即每天有 $k$ 位顾客来面包店，每人买一个面包（面包按照上述顺序售卖）。如果当天没有面包了，顾客就什么也买不到。在最后一天的清仓大甩卖中，所有剩余面包都会被卖出（这些面包同样计入“吸引力差”的计算）。 Monocarp 分析了竞争对手的数据，得出了 $m$ 个可能的顾客需求值 $k_1, k_2, \dots, k_m$。现在他想知道，对于每一个需求值，面包店的吸引力差是多少。你能帮他计算吗？

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 2 \times 10^5$；$1 \le m \le 2 \times 10^5$），分别表示面包店营业的天数和可能的顾客需求数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示每天早上烤好的面包数量。 第三行包含 $m$ 个整数 $k_1, k_2, \dots, k_m$（$1 \le k_1 < k_2 < \dots < k_m \le 10^9$），表示按升序排列的可能顾客需求值。

输出 $m$ 个整数，对于每一个顾客需求，输出面包店的吸引力差。

以第一个样例为例，描述几种顾客需求下的情况： 如果顾客需求为 $1$： - 第 $1$ 天：烤了 $5$ 个面包，只卖出 $1$ 个，变质度为 $1-1=0$； - 第 $2$ 天：还剩 $4$ 个面包，又烤了 $2$ 个。只卖出 $1$ 个，是当天烤的，变质度 $2-2=0$； - 第 $3$ 天：还剩 $4$ 个第一天的面包和 $1$ 个第二天的面包。又烤了 $1$ 个，只卖出当天烤的，变质度 $3-3=0$； - 第 $4$ 天：还剩 $4$ 个第一天的面包和 $1$ 个第二天的面包。又烤了 $3$ 个，只卖出当天烤的，变质度 $4-4=0$； - 第 $5$ 天：还剩 $4$ 个第一天的面包、$1$ 个第二天的面包、$2$ 个第四天的面包。又烤了 $7$ 个面包，由于这是最后一天，所有 $14$ 个面包都卖出。$4$ 个第一天的面包最大变质度为 $5-1=4$。 因此，面包店的吸引力差为 $4$。如果顾客需求为 $10$，则所有面包都会在当天卖出，变质度均为 $0$。 由 ChatGPT 4.1 翻译