33437번 - Card Game 다국어

문제

Randias is playing a card game. In this game, each card has a number written on it. For cards with numbers $a_{1}, a_{2}, \ldots, a_{m},ドル Randias will play the game in the following way.

Initially, all cards are in his hand. Randias will maintain a card sequence (initially empty). In the $i$-th operation, Randias will put the $i$-th card (this card has number $a_{i}$ written on it) at the end of the card sequence. Then:

• If there are no other cards in the sequence with number $a_{i}$ written on them, the $i$-th operation ends.
• Otherwise, let the $j$-th card in the card sequence have number $a_{i}$ written on it. Randias will take away all cards between the $j$-th card and the newly placed card, including the $j$-th card and the newly placed card.

For example, let $a = [2, 1, 3, 1, 2, 3],ドル and the card sequence $s = []$ initially.

After the 1ドル$-st operation, $s = [2]$.

After the 2ドル$-nd operation, $s = [2, 1]$.

After the 3ドル$-rd operation, $s = [2, 1, 3]$.

After the 4ドル$-th operation, $s = [2]$ (cards 1,ドル 3, 1$ are taken away).

After the 5ドル$-th operation, $s = []$ (cards 2,ドル 2$ are taken away).

After the 6ドル$-th operation, $s = [3]$.

Now, Randias is given $n$ cards $a_{1}, a_{2}, \ldots, a_{n}$. He has $q$ queries. The $i$-th query is a pair of integers $\ell_{i}, r_{i}$. With this query, Randias wants to know how many cards will be left in the card sequence if the initial list of cards is $a_{\ell_{i}}, a_{\ell_{i} + 1}, \ldots, a_{r_{i}}$.

For some reason, Randias hopes you can answer the questions online. That is, you need to decode the next question with the answer for the previous question.

입력

The first line contains two integers $n$ and $q$ (1ドル \le n, q \le 3 \cdot 10^5$) denoting the number of cards and the number of queries.

The following line contains $n$ integers $a_{1}, a_{2}, \ldots, a_{n}$ (1ドル \le a_{i} \le n$).

Each of the following $q$ lines contains two integers $\ell'_{i}$ and $r'_{i}$ (0ドル \le \ell'_{i} ,r'_{i} \le 2n$). Let the answer for the last query is $\mathit{lastans}$. Then $\ell_{i} = \ell'_{i} \oplus \mathit{lastans}$ and $r_{i} = r'_{i} \oplus \mathit{lastans}$ are the next query. In these formulas, $\oplus$ is the bitwise exclusive OR operation. It is guaranteed that, after decoding, 1ドル \le \ell_{i} \le r_{i} \le n$. If you haven't answered any queries before, $\mathit{lastans} = 0$.

출력

For each query, output a line with one integer: the answer to that query.

제한

노트

For the first example, the segments in the queries are $[5, 5],ドル $[2, 5],ドル $[1, 1],ドル $[1, 4],ドル and $[3, 5]$.