Card Game

Randias is playing a card game. Each card has a number written on it. For cards with numbers $a_{1}, a_{2}, \ldots, a_{m}$, Randias plays the game as follows.

Initially, all cards are in his hand. Randias maintains a card sequence, which starts empty. In the $i$-th operation, he puts the $i$-th card (number $a_{i}$) at the end of the sequence. Then:

• If no other card in the sequence has the number $a_{i}$, the $i$-th operation ends.
• Otherwise, let the $j$-th card in the sequence have the number $a_{i}$. Randias takes away all cards from the $j$-th card through the newly placed card, inclusive.

For example, let $a = [2, 1, 3, 1, 2, 3]$ and let the card sequence $s = []$ initially. After operation 1, $s = [2]$. After operation 2, $s = [2, 1]$. After operation 3, $s = [2, 1, 3]$. After operation 4, $s = [2]$ (cards 1, 3, 1 are taken away). After operation 5, $s = []$ (cards 2, 2 are taken away). After operation 6, $s = [3]$.

Randias is given $n$ cards $a_{1}, a_{2}, \ldots, a_{n}$ and $q$ queries. The $i$-th query is a pair $\ell_i, r_i$. For each query, find how many cards remain in the sequence if the initial list of cards is $a_{\ell_i}, a_{\ell_i+1}, \ldots, a_{r_i}$. The queries must be answered online, so each query is decoded using the answer to the previous one.

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 3 \cdot 10^5$).

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

Each of the next $q$ lines contains two integers $\ell'_i$ and $r'_i$ ($0 \le \ell'_i, r'_i \le 2n$). Let $lastans$ be the answer to the previous query. Then $\ell_i = \ell'_i \oplus lastans$ and $r_i = r'_i \oplus lastans$ are the decoded query. Here $\oplus$ is the bitwise exclusive OR. It is guaranteed that after decoding, $1 \le \ell_i \le r_i \le n$. If no query has been answered yet, $lastans = 0$.

For each query, print one line with the answer.

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