G. If Sort is Life
time limit per test
13 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a permutation $$$p$$$ of length $$$n$$$.

You are allowed to do the following operation :

  • Choose any $$$i,j(1 \le i, j \le n)$$$ such that |$$$i - j$$$| is odd, then swap $$$p_i$$$ and $$$p_j$$$.

Let $$$f(p)$$$ denotes the minimum number of operations required to sort $$$p$$$ in ascending order.

Find the value of $$$f(p)$$$ and also answer the $$$q$$$ queries :

  • x y : swap $$$p_x$$$ and $$$p_y$$$ and find the value of $$$f(p)$$$. Note that these updates are persistent, that is changes made to the $$$p$$$ will apply when processing future updates.
Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n,q$$$ $$$(2 \le n,q \le 5 \cdot 10^4)$$$ — the length of the permutation and the number of queries.

The second line of each test case contains $$$n$$$ integers $$$p_1,p_2,\cdots,p_n$$$ ($$$1 \le p_{i} \le n$$$).

The next $$$q$$$ lines of each test case contains two integers $$$x,y$$$ $$$(1 \le x \lt y \le n)$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^4$$$.

It is guaranteed that the sum of $$$q$$$ over all test cases does not exceed $$$5 \cdot 10^4$$$.

Output

For each test case, print $$$q+1$$$ space separated integers — the value of $$$f(p)$$$.

Example
Input
2
5 3
3 1 2 5 4
1 3
4 5
1 2
7 5
7 3 5 1 2 4 6
2 3
1 4
3 7
1 5
4 5
Output
3 2 1 0 
5 4 3 4 5 6