Given an integer sequence $a_1, \dots, a_n$ such that there do not exist $1 \le i < j < k < l \le n$ where $a_i = a_j = a_k = a_l$.

There are $m$ operations. Each operation provides an integer $x$. First, perform a modification: reverse the prefix $a_1, a_2, \dots, a_x$ to $a_x, \dots, a_2, a_1$. Then, query how many distinct values $k$ exist such that there exist $1 \le i \le x < j \le n$ with $a_i = a_j = k$.

Input

The first line contains two integers $n$ and $m$.

The second line contains $n$ integers representing $a_1, \dots, a_n$.

The next $m$ lines each contain an integer $x$, representing an operation.

Output

Output $m$ lines, each containing an integer representing the answer to the query for each operation.

Examples

Input 1

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

Output 1

1
1
1
2
0

Subtasks

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078

For $100\%$ of the data, all values are integers, $1 \le a_i \le n$, $1 \le x \le n$, and $n, m \le 5 \times 10^5$.