P9677 [ICPC 2022 Jinan R] Stack Sort

给定一个包含 $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$。

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