T580714 「2025 扬大ACM选拔赛」C - Kaguya wanna Sort

Kaguya is given a permutation with $n$ numbers, $a_1, a_2, \dots, a_n ~~ (1\leq a_i\leq n, a_i\neq a_j\textrm{ when }i\neq j)$. Kaguya wants to sort these numbers using $m$ stacks. Specifically, she should complete the following task: Initially, all stacks are empty. She needs to push each number $a_i$ to the top of one of the $m$ stacks one by one, in the order of $a_1,a_2,\ldots, a_n$. **After pushing all numbers in the stacks**, Kaguya pops all the elements from the stacks in a clever order so that the first number she pops is $1$, the second number you pop is $2$, and so on. **If Kaguya pops an element from a stack $S$** , **she cannot pop any element from the other stacks until $S$ becomes empty.** What is the minimum possible $m$ to complete the task?

**There are multiple test cases.** The first line contains one integer $T ~~ (1\le T \le 10^5)$, denoting the number of test cases. **For each test case:** The first line contains one positive integer $n ~~ (1\le n \le 5 \times 10^5)$. The next line contains $n$ integers $a_1,\ldots, a_n ~~ (1 \le a_i\le n)$，denoting the permutation. It is guaranteed that $a_1,\ldots, a_n$ form a permutation, i.e. $a_i\neq a_j$ for $i \neq j$. The $\sum n$ over all test cases will not exceed $5\times 10^5$.

**For each test case:** Output the minimum possible $m$ in one line.