410685: GYM104076 K Stack Sort

You are 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)$$$.

You want to sort these numbers using $$$m$$$ stacks. Specifically, you should complete the following task:

Initially, all stacks are empty. You need 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, you pop all the elements from the stacks in a clever order so that the first number you pop is $$$1$$$, the second number you pop is $$$2$$$, and so on. If you pop an element from a stack $$$S$$$, you cannot pop any element from the other stacks until $$$S$$$ becomes empty.

What is the minimum possible $$$m$$$ to complete the task?

The first line contains one integer $$$T~(1\le T \le 10^5)$$$, 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$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases is no more than $$$5\times 10^5$$$.

For each test case, output the minimum possible $$$m$$$ in one line.

3
3
1 2 3
3
3 2 1
5
1 4 2 5 3

3
1
4