Ken Googler the keen koala loves playing Whac-A-Mole at the annual koala carnival. His skill and dexterity make him one of the best Whac-A-Mole players in the west, and to reward his success, the carnival administrator presents him with a line of ~N~ stuffed animals, ~a~, for him to choose from. He allows Ken to choose any contiguous section of stuffed animals from the line, as long as they are all unique. Upon sight, Ken knows that he wants all the stuffed animals in the range from ~l_i~ to ~r_i~ inclusive. Being a greedy fellow, Ken also wants as many extra stuffed animals as possible on either side, along with the stuffed animals in the given range.

Being the dedicated Whac-A-Mole player he is, he returns to the carnival every day over the next ~Q~ days. Each day, he has a new range of stuffed animals that he wants; the stuffed animals that were chosen on a previous day are replaced by the next morning. On each day, help Ken find the length of the maximum contiguous section of stuffed animals he can take containing the interval from ~l_i~ to ~r_i~ inclusive. Suspicious that Ken is receiving help, the carnival administrator asks Ken for the section he wants immediately after asking.

For this problem, Python users are recommended to use PyPy over CPython.

Constraints

~1 \le N \le 10^6~

~1 \le l \le r \le N~

~1 \le Q \le 2 \cdot 10^5~

~1 \le a_i \le N~

It is guaranteed that all stuffed animals within the range from ~l_i~ to ~r_i~ will be unique.

Subtask 1 [5%]

~1 \le N, Q \le 450~

Subtask 2 [15%]

~1 \le N, Q \le 2\,000~

Subtask 3 [80%]

No additional constraints.

Input Specification

The first line contains the integers ~N, Q~.

The next line contains the integers ~a_1, a_2, \dots, a_N~.

Note that the input will be online enforced. The next ~Q~ lines each contain ~2~ encrypted integers ~p, q~. Given this pair, ~l,r~ can be found by ~p \oplus \text{lastAns}~ and ~q \oplus \text{lastAns}~ respectively, where ~\text{lastAns}~ is the answer to the previous query or ~0~ for the first query. ~\oplus~ denotes the bitwise XOR operation.

Output Specification

For each unencrypted query ~l, r~, output the length of the longest section of the line ~a_x, a_{x+1}, \dots, a_y~ such that ~1 \le x \le l \le r \le y \le N~ and all the elements in the section are distinct. The answer to each query should be on a separate line.

Sample Input 1

5 3
4 5 3 3 2
5 5
3 1
0 0

Sample Input 1 (Unencrypted)

5 3
4 5 3 3 2
5 5
1 3
3 3

Sample Output 1

2
3
3

Explanation for Sample 1

For the first query, Ken must take the fifth stuffed animal. He can also take the fourth stuffed animal, but cannot take the third since it is identical to the fourth. Ken should choose the interval from ~4~ to ~5~.

For the second query, Ken should choose the interval from ~1~ to ~3~.

For the third query, Ken should choose the interval from ~1~ to ~3~.

Sample Input 2

8 5
6 8 2 5 6 7 8 3
3 4
0 14
7 4
7 7
1 14

Sample Input 2 (Unencrypted)

8 5
6 8 2 5 6 7 8 3
3 4
6 8
1 2
3 3
7 8

Sample Output 2

6
6
4
6
6