如果 $$$m$$$ 整数序列包含从 $$$1$$$ 到 $$$m$$$ 的所有整数恰好一次,则该序列称为排列。数字 $$$m$$$ 称为排列的长度。
Dreamoon 有两种非零长度 $$$l_1$$$ 和 $$$l_2$$$ 的排列 $$$p_1$$$ 和 $$$p_2$$$。
现在 Dreamoon 将这两个排列连接成另一个长度为 $$$l_1 + l_2$$$ 的序列 $$$a$$$。 $$$a$$$ 的第一个 $$$l_1$$$ 元素是排列 $$$p_1$$$,$$$a$$$ 的下一个 $$$l_2$$$ 元素是排列 $$$p_2$$$。
给定序列 $$$a$$$,你需要找到两个排列 $$$p_1$$$ 和 $$$p_2$$$。如果有多种可能的方法来恢复它们,您应该找到所有这些方法。 (注意,也有可能没有办法。)
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10\,000$$$) 表示输入中测试用例的数量。
每个测试用例包含两行。第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 200\,000$$$):$$$a$$$ 的长度。第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n-1$$$)。
$$$n$$$ 的总和小于 $$$200\,000$$$。
输出
对于每个测试用例,输出的第一行应包含一个整数 $$$k$$$:将 $$$a$$$ 划分为排列 $$$p_1$$$ 和 $$$p_2$$$ 的方法数。
接下来的 $$$k$$$ 行应包含两个整数 $$$l_1$$$ 和 $$$l_2$$$ ($$$1 \leq l_1, l_2 \leq n, l_1 + l_2 = n$$$),表示可以将 $$$a$$$ 分为长度 $$$l_1$$$ 和 $$$l_1$$$ 的两个排列$$$l_2$$$($$$p_1$$$ 是 $$$a$$$ 的第一个 $$$l_1$$$ 元素,$$$p_2$$$ 是 $$$a$$$ 的最后一个 $$$l_2$$$ 元素)。您可以按任何顺序打印解决方案。
示例
输入 #1
6 5 1 4 3 2 1 6 2 4 1 3 2 1 4 2 1 1 3 4 1 3 3 1 12 2 1 3 4 5 6 7 8 9 1 10 2 3 1 1 1
输出 #1
2 1 4 4 1 1 4 2 0 0 1 2 10 0
注意
在第一个示例中,将 $$$a$$$ 划分为排列的两种可能方法是 $$$\{1\} + \{4, 3, 2, 1\}$$$ 和 $$$\{1,4,3,2\} + \{1\}$$$。
在第二个示例中,将 $$$a$$$ 划分为排列的唯一方法是 $$$\{2,4,1,3\} + \{2,1\}$$$。
在第三个示例中,没有可能的方法。