题目描述

你想要借助 $k$ 个栈将序列 $a[1 \ldots n]$ 排成非降序。 开始时栈都为空，可以进行3种㨐作:

• $(1, i)$ : 取出当前 $a$ 序列的最后一个元素，push 到第 $i$ 个栈中;
• $(2, i)$ : pop第 $i$ 个栈 (需保证不为空)，并将栈顶元素插入到输出序列 $b$ 的末尾；
• $(3, i, j)$ : pop 第 $i$ 个栈 (需保证不为空)，并将栈顶元素 push 到第 $j$ 个栈中;

注意不能把当前 $a$ 序列的末尾元索直接放到输出序列 $b$ 中。 睿智的你一下就想到了如果持有的栈的个数 $k$ 大等于数字总个数 $n$ ，那么一定可以完成这项排序工作。 现在请问，完成排序工作最少需要多少个栈，即 $k$ 的最小值。 接着你需要输出任意一个合法的操作方案，使得输出序列 $b$ 为非降序。

输入格式

第一行 1 个整数 $T$ ，代表有 $T$ 组数据 每组数据的第一行 1 个整数 $n$ ，代表序列长度 第二行 $n$ 个正整数 $a[i]$ ，代表序列中的元索

输出格式

对于每组数据，首先输出一行一个整数 $k$ 代表最少需要 $k$ 个栈 第二行输出一个整数 $m$ ，代表操作方案有 $m$ 行。 接下来 $m$ 行，你需要按以下格式输出操作方案:

• $(1, i, c)$ : 重复进行 $c$ 次 1 操作
• $(2, i)$ : 进行 1 次 2 操作
• $(3, i, j, c)$ : 重复进行 $c$ 次操作

对于每组数据，你需要保证 $m \leq \max \left(10^4, 5 n\right)$ ，操作中 $1 \leq i \neq j \leq k$ 。

请注意本题的输出量较大，请使用快速的输出方式（如printf）。本题使用special judge进行评测，评测比较慢，提交后需要等待一段时间才能有结果

3
3
3 2 1
2
1 1
3
2 3 1

1
6
1 1 1
2 1
1 1 1
2 1
1 1 1
2 1
1
4
1 1 1
1 1 1
2 1
2 1
1
6
1 1 1
2 1
1 1 1
1 1 1
2 1
2 1

数据规模与约定

对于测试点1-3， $1 \leq n \leq 5$

对于测试点4-6， $1 \leq n \leq 100$

对于测试点7-8， $1 \leq n \leq 10^5, 1 \leq a[i] \leq 2$

对于测试点9-10， $1 \leq a[i], n \leq 10^5$

对于所有测试点， $T \leq 100,1 \leq a[i], n \leq 10^5, \sum n \leq 3 \times 10^5$

大样例

大样例下载