Perm

Se dă o permutare $P[1], \dots , P[N]$ de $N$ numere. Un ciclu al permutării este un șir $i_1, \dots, i_k \in \{1, \dots, N \}$ astfel încât $i_2 = P[i_1]$, $i_3 = P[i_2]$, $\dots$, $i_k = P [i_{k - 1}]$, $i_1 = P [i_k]$. Un interval $[x, y]$ este bun dacă există un ciclu $i_1, \dots, i_{y-x+1}$ astfel încât fiecare număr $x, x + 1, \dots , y$ să apară exact o dată în $i_1, \dots , i_{y-x+1}$.

O interogare constă din două valori $x$ și $y$, cu $1 ≤ x ≤ y ≤ N$. Răspunsul este numărul minim de interschimbări ce trebuie aplicate asupra permutării inițiale astfel încât intervalul $[x, y]$ să devină bun. O interschimbare constă în a selecta două poziții $i$ și $j$ și a schimba valorile $P [i]$ și $P [j]$ între ele.

Atenție! Interogările sunt independente; adică, interschimbările aplicate pentru o interogare nu sunt păstrate la interogările ce urmează. Mai mult, pentru interogarea $[x, y]$ este voie să interschimbăm elemente din intervalul $[x, y]$ cu elemente din afara intervalului $[x, y]$.

Cerință

Să se afișeze răspunsul pentru $Q$ interogări.

Date de intrare

Fișierul de intrare perm.in conține pe prima linie două numere $N$ și $Q$.

Pe a doua linie se vor afla $N$ valori reprezentând, în ordine, valorile $P [1], P [2], \dots, P [N ]$.

Pe următoarele $Q$ linii se vor afla câte două numere $x$, $y$ separate printr-un spațiu, reprezentând câte o întrebare.

Date de ieșire

Fișierul de ieșire perm.out trebuie să conțină $Q$ linii, pe fiecare răspunsul pentru câte o interogare.

Restricții și precizări

• $1 \leq N, Q \leq 300 \ 000$
• $1 \leq x \leq y \leq N$

Exemplu

perm.in

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

perm.out

1
0
1

Explicație

• Pentru a transforma intervalul $[2, 4]$ într-un interval bun, este suficient să facem o singură interschimbare între poziția $1$ și poziția $2$.
• Intervalul $[1, 4]$ este deja bun, deci nu avem nevoie de nicio interschimbare.
• Pentru ultimul interval, avem nevoie de o singură interschimbare între poziția $1$ și poziția $5$.