题目描述

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

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

• 每次选择一个大于 $k$ 的正整数 $a_i $，将 $ai$ 减去 $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$ 对应的答案。

样例

input

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

output

5 5 2 1 1 0

数据范围与提示

对于 $100\%$ 的数据，有 $1\le n\le 1\ 000\ 000,1\le m\le 50,1\le a_i,k\le 10^9$。

Translated by vincent163