题目描述

译自 POI 2010 Stage 2. Day 1「Blocks」

给出 $n$ 个正整数 $a_1, a_2, \cdots, a_n$，再给出一个正整数 $k$，现在可以进行如下操作：

每次选择一个大于 $k$ 的正整数 $a_i$，将 $a_i$ 减去 $1$，选择 $a_{i-1}$ 和 $a_{i+1}$ 中的一个加上 $1$。 经过一定次数的操作后，问最大能够选出多长的一个连续子序列，使得这个子序列的每个数都不小于 $k$。 总共给出 $m$ 次询问，每次询问给出的 $k$ 不同，你需要分别回答。

输入格式

第一行两个空格隔开的正整数 $n, m$。 第二行 $n$ 个空格隔开的正整数 $a_1, a_2, \cdots, a_n$。 第三行 $m$ 个空格隔开的正整数，表示每次询问的 $k$。

输出格式

一行，$m$ 个空格隔开的整数，第 $i$ 个数表示第 $i$ 次询问的 $k$ 对应的答案。

样例 输入

5 6
1 2 1 1 5
1 2 3 4 5 6

输出

5 5 2 1 1 0

数据范围与提示 对于 $100\%$ 的数据，有 $1 ≤ n ≤ 1\,000\,000$, $1 ≤ m ≤ 50$, $1 ≤ a_i, k ≤ 10^9$。

Translated by vincent163。