Permutare

Fie o permutare $P$ de lungime $N$. Considerăm operația de interschimbare de valori aflate pe două poziții consecutive.

Definim o permutare de lungime $N$ ca fiind un șir care conține toate numerele de la $0$ la $N-1$ exact odată. Fie o permutare $P = (p_0, p_1, p_i, p_{i+1}, p_{N-1})$ și un indice $0 \le i < N - 1$. În urma interschimbării valorilor aflate pe pozițiile $i$ și $i + 1$ din $P$, permutarea $P$ devine $P = (p_0, p_1, p_{i+1}, p_i, p_{N-1})$.

Concurentul (adică tu) poate cumpăra astfel de interschimbări. Odată cumpărată, o interschimbare poate fi folosită de oricâte ori. Definim costul lui $P$ ca fiind numărul minim de astfel de interschimbări ce trebuie cumpărate astfel încât permutarea să poată fi sortată folosind doar interschimbările cumpărate, fiecare de oricâte ori.

Comisia (adică noi) schimbă de $Q$ ori permutarea $P$ prin interschimbarea valorilor de pe două poziții arbitrare, nu neapărat adiacente. Odată făcută o schimbare asupra permutării, ea rămâne valabilă în continuare.

Atât pentru permutarea inițială, cât și pentru permutările obținute după fiecare dintre schimbările comisiei, se cere costul lui $P$.

Protocol de interacțiune

Concurentul va implementa două funcții init și query, cu următoarele semnături:

int init (std::vector<int> p);
int query (int x, int y);

Funcția init:

• Va fi apelată o singura dată, la începutul fiecărui test.
• Primește permutarea inițială $P$, de lungime $N$.
• Trebuie să întoarcă o singură valoare, reprezentand costul permutarii $P$.
  Funcția query:
• Va fi apelată de mai multe ori ($Q$ ori) pe parcursul unui test.
• Primește interschimbarea facută de comisie $(0 \le x < y < N)$. Este posibil că $y \neq x + 1$.
• Trebuie să întoarcă o singură valoare, reprezentand costul permutarii $P$ dupa aplicarea schimbării.

Concurentul NU va implementa o funcție main.

Subtask 1 (6 puncte)

• $1 \le N \le 1\ 000$
• $1 \le Q \le 10$

Subtask 2 (13 puncte)

• $2 \le N \le 100\ 000$
• $1 \le Q \le 100$

Subtask 3 (46 puncte)

• $2 \le N \le 50\ 000$
• $1 \le Q \le 50\ 000$

Subtask 4 (22 puncte)

• $2 \le N \le 100\ 000$
• $1 \le Q \le 200\ 000$
• Schimbările făcute de comisie interschimbă doar valori de pe poziții adiacente. Mai exact, $y = x + 1$ pentru toate schimbarile comisiei.

Subtask 5 (13 puncte)

• $2 \le N \le 100\ 000$
• $1 \le Q \le 200\ 000$

Exemple

Input

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

Output

0
1
0
2
2

Input

4 6
0 3 2 1
1 2
1 3
0 2
0 1
1 2
0 2

Output

2
2
1
3
3
2
3

Explicații

Pentru primul exemplu:
În permutarea inițială, $(0, 1, 2)$, nu este nevoie de nicio interschimbare pentru a sorta permutarea.

În permutarea de după prima schimbare, $(1, 0, 2)$, este nevoie de cumpărarea interschimbarii $(0, 1)$.

Permutarea de după a doua schimbare este indentică cu cea inițială.

Penultima permutare este $(2, 0, 1)$ și este nevoie de cumpărarea transpozițiilor $(0, 1)$ și $(1, 2)$.

Ultima permutare este $(2, 1, 0)$, iar interschimbarile $(0, 1)$ și $(1, 2)$ rămân ambele necesare (chiar dacă sunt folosite de mai multe ori, fiecare este cumpărată doar o dată).