← 返回题目列表

Codeforces · 1330/B

B. Dreamoon 喜欢排列

中文机器翻译题面 查看原题

如果 $$$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\}$$$。

在第三个示例中,没有可能的方法。