在制造出属于自己国家的汽车的道路上，跳蚤国王需要考虑的最后一道加工环节便是汽车整车装配，即把数以百计、或数以千计的各种零部件按照严格的技术要求组装成一辆完整的汽车。然而，这一环节远比跳蚤国王想像得要复杂，于是他找来了助手伏特和聪明的你。

汽车整车装配是一个工业问题，也是一个数学问题。如果把零部件按从小到大依次编号为 $1$ 到 $n$，那么装配的过程可以看成一个排列 $a$，其中第 $i$ 个位置为 $a_i$ 表示第 $i$ 步会把第 $a_i$ 号零件拼到汽车上去。

跳蚤国王自然不满足于只生产一辆汽车。一旦装配工厂建成，跳蚤国王希望看到装配工厂能无穷无尽地装配汽车。数学上，装配工厂需要进行的装配任务，便是排列 $a$ 重复无穷多次之后得到的结果，这里可以记为序列 $a^{\prime }$。

装配过程的真正难点在于，跳蚤国的装配机器有一定的技术缺陷，只有在上一次装配的零部件大小大于等于当前装配的零部件大小时，机器才能运转得很快，否则就会花很多时间来调整自身的配置。

因此，如果想执行装配任务序列 $a^{\prime }$ 中前 $x$ 项任务，那么伏特需要先将这 $x$ 项任务划分成若干个非严格递减的子序列，然后将这些任务子序列分配到不同的机器上去。现在伏特想知道，对于每一个他所关心的 $x$，最少能划分出多少个非严格递减的子序列呢？

形式化的题意：给定一个 $1\sim n$ 的排列 $a$。设 $a^{\prime }$ 为 $a$ 重复 $+\mathrm{\infty }$ 次得到的序列。给定 $m$ 组询问，每次给定一个 $x$，你需要求出 $a^{\prime }$ 中长度为 $x$ 的前缀最少能被划分成多少个子序列，使得 (1) 每个子序列非严格递减；(2) 该前缀中的每个位置都被划分给了恰好一个子序列。

输入格式

输入的第一行包含两个整数，表示 $n$ 与 $m$。

接下来共 $n$ 个整数，表示 $a_1,a_2,\cdots ,a_n$。

接下来 $m$ 行，每行一个整数，表示一组询问中的 $x$。

输出格式

共 $m$ 行，每行一个整数，依次表示每一组询问的答案。

样例一

input

5 3
2 4 3 1 5
4
8
12

output

2
3
4

explanation

$(a_1^{\prime },\dots a_4^{\prime })=(2,4,3,1)$，一种可能的答案为 $(2),(4,3,1)$。

$(a_1^{\prime },\dots ,a_8^{\prime })=(2,4,3,1,5,2,4,3)$，一种可能的答案为 $(2,1),(4,3,2),(5,4,3)$。

$(a_1^{\prime },\dots ,a_{12}^{\prime })=(2,4,3,1,5,2,4,3,1,5,2,4)$，一种可能的答案为 $(2,1),(4,3,2,1),(5,4,3,2),(5,4)$。

样例二

见附件下载，该样例满足子任务 $1$ 的限制。

样例三

见附件下载，该样例满足子任务 $3$ 的限制。

样例四

见附件下载，该样例满足子任务 $4$ 的限制。

样例五

见附件下载，该样例满足子任务 $5$ 的限制。

数据范围

对于 $100\mathrm{\%}$ 的数据，$1\le n\le 2\times {10}^5,1\le m\le {10}^6,1\le x\le {10}^{18}$，$a$ 是一个 $1\sim n$ 的排列。

时间限制：$5\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$