给定一个大小为 $n$ 的排列 $p$，定义 $f(i,j)$ 表示为交换 $p_i$ 和 $p_j \ (1\le i\le j\le n)$ 后子排列数组的数量。

例如，如果 $p=[5,1,4,2,3]$，我们选择 $i=2$，$j=3$，则结果数组将变为 $[5,4,1,2,3]$，故 $f(2,3)=5$。如果我们选择 $i=j=5$，则结果数组将保持不变，仍为 $[5,1,4,2,3]$，故 $f(5,5)=4$。

给定 $q$ 个询问，你的任务是对每次询问求第 $k$ 小的 $f(i,j) \ (1\le i\le j\le n)$ 。

注意:

• 长度为 $n$ 的排列是一个由 $1$ 到 $n$ 的 $n$ 个不同整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是一个排列（出现了重复的 $2$），$[1,3,4]$ 也不是一个排列（$n=3$ 但数组中有 $4$）。
• 数组 $a$ 是数组 $b$ 的子数组，当且仅当 $a$ 可以通过从 $b$ 中的开头和结尾删除一些（可能是零个或全部）元素而得到。
• 数组 $a$ 是数组 $b$ 的子排列数组，当且仅当 $a$ 是一个排列，并且 $a$ 是 $b$ 的一个子数组。

输入格式

从标准输入读入数据。

输入第一行包含两个整数 $s, n$，分别表示子任务编号，排列长度。对于样例，$s$ 表示该样例与测试点 $s$ 拥有相同的限制条件。

输入第二行包含 $n$ 个整数 $p_1,p_2,\cdots, p_n$，表示排列 $p$ 的元素。

输入第三行包含一个整数 $q$，表示询问数量。

接下来 $q$ 行，每行一个整数 $k$，表示一次询问。

输出格式

输出到标准输出。

对于每个询问，输出一行一个整数，表示第 $k$ 小的 $f(i,j) \ (1\le i\le j\le n)$ 。

样例

输入

1 10
10 9 5 6 8 4 3 2 7 1
4
18
15
14
55

输出

4
3
3
7

样例二

见下载目录下的 ex_2.in 与 ex_2.ans。

该组样例满足子任务 4 的条件。

样例三

见下载目录下的 ex_3.in 与 ex_3.ans。

该组样例满足子任务 8 的条件。

样例四

见下载目录下的 ex_4.in 与 ex_4.ans。

该组样例满足子任务 9 的条件。

子任务

对于所有测试数据，保证 $1 \le n \le 5 \times 10^{5}, 1 \le q \le 5 \times 10^{5}, 1\le k \le \frac{n(n+1)}{2}$。

​

特殊性质 A：对于唯一的一次询问，$k = 1$。

特殊性质 B：对于唯一的一次询问，$k = \frac{n(n+1)}{2}$；