407536: GYM102823 E Cartesian Tree

The Cartesian tree for a sequence of distinct numbers can be uniquely defined by the following properties:

The Cartesian tree for a sequence has one node for each number in the sequence. Each node is associated with a single sequence value.

A symmetric (in-order) traversal of the tree results in the original sequence. That is, the left subtree consists of the values earlier than the root in the sequence order, while the right subtree consists of the values later than the root, and a similar ordering constraint holds at each lower node of the tree.

The tree has the heap property: the parent of any non-root node has a larger value than the node itself.

$$$-$$$Wikipedia

It is quite easy to build a Cartesian tree with an array of $$$N$$$ distinct numbers, right?

What if changing the array by exchanging the value in position $$$i$$$ and that in position $$$i+1$$$?

Now you need to answer the sum of absolute layer(height) change of the tree nodes for each of the $$$M$$$ successive changes.

The first line contains a single integer $$$T$$$ ($$$1\le T\le 20$$$), indicating the number of test cases.

For each test case, the first line contains two integers $$$N$$$ ($$$2 \le N \le 10^5$$$) and $$$M$$$ ($$$1\le M\le 10^5$$$), indicating the number of elements in the array and the number of queries.

The second line contains $$$N$$$ elements, indicating the elements in the array.

The next $$$M$$$ lines describe $$$M$$$ changes described above. Each line contains a 0-based index $$$i$$$ ($$$0\le i < N-1$$$), which indicates we want to swap the elements located in $$$i$$$ and $$$i + 1$$$.

For each test case, print Case $$$T$$$: at first line, in which $$$T$$$ is the test number. For each change, output the sum of absolute layer change of the tree nodes in a new line.

3
4 2
1 2 3 4
2
1
3 6
1 2 3
0
1
1
0
0
0
5 10
2 3 5 4 1
0
1
2
3
2
3
1
2
3
2

Case 1:
2
2
Case 2:
0
1
1
0
0
0
Case 3:
0
0
1
0
1
1
1
1
3
2

The first sample of Sample 1: