Given a permutation $p$ of size $n$, define $f(i,j)$ as the number of sub-permutation arrays after swapping $p_i$ and $p_j \ (1\le i\le j\le n)$.

For example, if $p=[5,1,4,2,3]$, and we choose $i=2$ and $j=3$, the resulting array becomes $[5,4,1,2,3]$, so $f(2,3)=5$. If we choose $i=j=5$, the resulting array remains unchanged, i.e., $[5,1,4,2,3]$, so $f(5,5)=3$.

Given $q$ queries, your task is to find the $k$-th smallest $f(i,j) \ (1\le i\le j\le n)$ for each query.

Note:

• A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in any order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not (the number $2$ appears twice), and $[1,3,4]$ is not (where $n=3$ but the array contains $4$).
• An array $a$ is a subarray of array $b$ if and only if $a$ can be obtained by deleting some (possibly zero or all) elements from the beginning and the end of $b$.
• An array $a$ is a sub-permutation array of array $b$ if and only if $a$ is a permutation and $a$ is a subarray of $b$.

Input

Read data from standard input.

The first line contains two integers $s$ and $n$, representing the subtask number and the permutation length, respectively. For the sample, $s$ indicates that the sample shares the same constraints as test case $s$.

The second line contains $n$ integers $p_1,p_2,\cdots, p_n$, representing the elements of the permutation $p$.

The third line contains an integer $q$, representing the number of queries.

The next $q$ lines each contain an integer $k$, representing a query.

Output

Output to standard output.

For each query, output one integer per line, representing the $k$-th smallest $f(i,j) \ (1\le i\le j\le n)$.

Examples

Input

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

Output

4
3
3
7

Note

See the files ex_2.in and ex_2.ans in the download directory. This set of samples satisfies the conditions of subtask 4.

See the files ex_3.in and ex_3.ans in the download directory. This set of samples satisfies the conditions of subtask 8.

See the files ex_4.in and ex_4.ans in the download directory. This set of samples satisfies the conditions of subtask 9.

Subtasks

For all test data, it is guaranteed that $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}$.

Special Property A: For the only query, $k = 1$.

Special Property B: For the only query, $k = \frac{n(n+1)}{2}$.