Malvika gets bored along with her Cats

Malvika's cats, Chingam and Jimma, are also bored of solving problems. Fortunately, Chingam has found $n$ dark chocolate bars. They all have the same width but differ in length, and no two bars have the same length. The bars are kept in a row, with lengths $L_1, L_2, \ldots, L_n$ from left to right. That is, bar $i$ has length $L_i$.

Chingam decided to play a small game with Jimma. In one step, Jimma chooses a bar that has not been eaten yet. Chingam hates inversions, so he instantly eats that bar, along with every other bar that forms an inversion pair with it. Bars $i$ and $j$ form an inversion pair when the bar on the left is longer than the bar on the right.

So if Jimma selects bar $i$, Chingam eats bar $i$, every bar $j$ with $j > i$ and $L_j < L_i$, and every bar $k$ with $k < i$ and $L_k > L_i$. Then the step ends, and the next step begins with Jimma selecting another bar. The process repeats until all $n$ bars are eaten.

Jimma does not like this game because she gets no chocolate. So she wants to finish it as soon as possible and go back to sleep. Find the minimum number of steps needed for the game to end.

The first line contains a single integer $T$, the number of test cases.

The first line of each test case contains one integer $n$.

The second line contains $n$ space-separated integers $L_1, L_2, \ldots, L_n$.

For each test case, output a single integer on its own line: the minimum number of steps needed for the game to end.

• $1 \le T \le 5$
• $1 \le n \le 10^5$
• $1 \le L_i \le n$

In the first step, Jimma can choose bar 4, which has length 2. Bars 3 and 1 form inversion pairs with bar 4, so Chingam eats all three bars. In the second step, Jimma chooses bar 2, and the game ends. You can check that Jimma cannot remove all four bars in one step.