Различные на отрезке, онлайн

Дан массив из $n$ чисел. Нужно отвечать на запросы «сколько различных значений на отрезке $[l, r]$», но границы приходят зашифрованными: по паре $(l_j, r_j)$ из входа настоящие границы получаются как

где $\text{prev}$ — ответ на предыдущий запрос ($0$ для первого). Если после расшифровки $l > r$, границы меняются местами.

В первой строке — числа $n$ и $q$ ($1 \le n, q \le 2 \cdot 10^5$). Во второй — $n$ чисел ($|a_i| \le 10^9$). В следующих $q$ строках — пары $l_j$, $r_j$ ($0 \le l_j, r_j \le 10^9$).

На каждый запрос выведите количество различных значений на расшифрованном отрезке.