题目描述

给定一个包含 $n$ 个数字的排列 $a_1, a_2, \dots, a_n (1\leq a_i\leq n, a_i \neq a_j\text{ 当 }i \neq j)$。

你需要使用 $m$ 个栈对这些数字进行排序。具体来说，你需要完成以下任务：

最初，所有栈都是空的。你需要按照 $a_1,a_2,\ldots, a_n$ 的顺序，将每个数字 $a_i$ 压入 $m$ 个栈中的一个栈的顶部。在将所有数字压入栈中之后，你需要以一种巧妙的顺序从栈中弹出所有元素，使得你弹出的第一个数字是 $1$，第二个数字是 $2$，依此类推。如果你从一个栈 $S$ 中弹出一个元素，那么在 $S$ 变空之前，你不能从其他栈中弹出任何元素。

完成任务所需的最小 $m$ 是多少？

输入格式

第一行包含一个整数 $T~(1\le T \le 10^5)$，表示测试用例的数量。

对于每个测试用例，第一行包含一个正整数 $n~(1\le n \le 5 \times 10^5)$。下一行包含 $n$ 个整数 $a_1,\ldots, a_n~(1 \le a_i\le n)$，表示排列。保证 $a_1,\ldots, a_n$ 形成一个排列，即 $a_i \neq a_j$ 对于 $i \neq j$。

保证所有测试用例中 $n$ 的总和不超过 $5\times 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示完成任务所需的最小 $m$。

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

3
1
4

提示

题面翻译由 ChatGPT-4o 提供。