Can BCD Run Without Difficulty Inversions?

The BCD contest has $N$ problems arranged in a fixed order. The difficulty of the problem currently at position $j$ is $A_j$. Every difficulty is an integer from $1$ to $M$, inclusive.

A participant with skill $s$ solves problems according to these rules.

• Start with the first problem and consider problems in order.
• If the current problem has difficulty at most $s$, solve it and move to the next problem. A difficulty equal to the participant's skill is also solvable.
• Stop immediately upon reaching the first problem whose difficulty exceeds $s$. The participant does not skip that problem or attempt any problem after it.
• If all problems have been solved, finish.

Thus, a participant solves no problems if the first problem is already too difficult, and solves all $N$ problems if every difficulty is at most their skill.

For each participant, compare the number of problems solved in the following two situations.

1. Apply the rules to the problems in their current order.
2. Rearrange the same problems in nondecreasing order of difficulty, then apply the rules again from the beginning.

If the two counts differ, call the participant a victim of Lunarity-style difficulty ordering. The order among problems of equal difficulty does not affect either count.

For example, suppose the difficulties are $(2,1,5,4)$ and a participant's skill is $4$. In the current order, the participant solves the first two problems and stops at the problem of difficulty $5$. They do not solve the later problem of difficulty $4$. In the sorted order $(1,2,4,$, they solve three problems. Therefore, the participant with skill is a victim.

There is exactly one participant with each skill $1,2,\ldots,M$. Find the number of victims of Lunarity-style difficulty ordering.

The input is given in the following format.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

For each test case, print the number of victims of Lunarity-style difficulty ordering on its own line.

• $1\leq T\leq200\,000$.
• $1\leq N\leq200\,000$.
• $1\le M$.