Dreamoon Likes Permutations

题意翻译

### 题目描述 一个长度为 $m$ 的数列被称为排列，当且仅当其中包含了 $1$ 到 $m$ 中所有整数恰好一次。$m$ 被称为这个排列的长度。 Dreamoon 得到了两个排列 $p_1, p_2$，长度分别为正整数 $l_1, l_2$。 现在 Dreamoon 要将这两个排列合并成一个长度为 $l_1 + l_2$ 的序列 $a$，其中开头的 $l_1$ 个数为排列 $p_1$，结尾的的 $l_2$ 个数为排列 $p_2$。 给出序列 $a$，你需要找到这两个排列 $p_1, p_2$。如果有多种可能的还原方式，你需要找到所有的答案。（注意，也有可能不存在可能的还原方式。） ### 输入格式 第一行输入一个整数 $t ~ (1 \le t \le 10\ 000)$，表示测试数据的组数。 对于每组测试数据，输入两行。 第一行输入一个整数 $n ~ (2 \le n \le 200\ 000)$，表示 $a$ 的长度。 第二行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n ~ (1 \le a_i \le n - 1)$。 每组测试数据中 $n$ 的和不超过 $200\ 000$。 ### 输出格式 对于每组测试数据，第一行输出一个整数 $k$，表示有 $k$ 种方案将 $a$ 分成两个排列 $p_1$ 和 $p_2$。 接下来的 $k$ 行，每行输出两个整数 $l_1, l_2 ~ (1 \le l_1, l_2 \le n; l_1 + l_2 = n)$，表示存在一种还原方案，将 $a$ 分割成两个长度分别为 $l_1$ 和 $l_2$ 的排列（$p_1$ 是 $a$ 的前 $l_1$ 个元素，$p_2$ 是 $a$ 的后 $l_2$ 个元素）。你可以以任意顺序输出。 ### 说明/提示 在第一组数据中，两种可能的将 $a$ 分为两个排列的还原方式为 $\{1\} + \{4, 3, 2, 1\}$ 和 $\{1, 4, 3, 2\} + \{1\}$。 在第二组数据中，唯一一种可能的划分方式为：$\{ 2, 4, 1, 3\} + \{2, 1\}$。 在第三种数据中，不存在可能的还原方式。

题目描述

The sequence of $ m $ integers is called the permutation if it contains all integers from $ 1 $ to $ m $ exactly once. The number $ m $ is called the length of the permutation. Dreamoon has two permutations $ p_1 $ and $ p_2 $ of non-zero lengths $ l_1 $ and $ l_2 $ . Now Dreamoon concatenates these two permutations into another sequence $ a $ of length $ l_1 + l_2 $ . First $ l_1 $ elements of $ a $ is the permutation $ p_1 $ and next $ l_2 $ elements of $ a $ is the permutation $ p_2 $ . You are given the sequence $ a $ , and you need to find two permutations $ p_1 $ and $ p_2 $ . If there are several possible ways to restore them, you should find all of them. (Note that it is also possible that there will be no ways.)

输入输出格式

输入格式

The first line contains an integer $ t $ ( $ 1 \le t \le 10\,000 $ ) denoting the number of test cases in the input. Each test case contains two lines. The first line contains one integer $ n $ ( $ 2 \leq n \leq 200\,000 $ ): the length of $ a $ . The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq n-1 $ ). The total sum of $ n $ is less than $ 200\,000 $ .

输出格式

For each test case, the first line of output should contain one integer $ k $ : the number of ways to divide $ a $ into permutations $ p_1 $ and $ p_2 $ . Each of the next $ k $ lines should contain two integers $ l_1 $ and $ l_2 $ ( $ 1 \leq l_1, l_2 \leq n, l_1 + l_2 = n $ ), denoting, that it is possible to divide $ a $ into two permutations of length $ l_1 $ and $ l_2 $ ( $ p_1 $ is the first $ l_1 $ elements of $ a $ , and $ p_2 $ is the last $ l_2 $ elements of $ a $ ). You can print solutions in any order.

输入输出样例

输入样例 #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

说明

In the first example, two possible ways to divide $ a $ into permutations are $ \{1\} + \{4, 3, 2, 1\} $ and $ \{1,4,3,2\} + \{1\} $ . In the second example, the only way to divide $ a $ into permutations is $ \{2,4,1,3\} + \{2,1\} $ . In the third example, there are no possible ways.