Background

Problem Description

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

There are $m$ operations. In each operation, an integer $x$ is given. First, perform a modification: reverse $a_1,a_2,\dots,a_x$ into $a_x,\dots,a_2,a_1$. Then query how many distinct values $k$ satisfy that there exist $1 \le i \le x < j \le n$ such that $a_i = a_j = k$.

Input Format

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

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

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

Output Format

Output $m$ lines. Each line contains one integer, representing the answer to the query for each operation in order.

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

1
1
1
2
0

Hint

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

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

Translated by ChatGPT 5