You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

传说中存在着一扇神秘的魔法大门，它通向着无尽的魔法宝藏。但是这扇大门只对那些能够熟练运用栈法杖的魔法师敞开。

大门的密码是一个序列 $a[1...n]$，为了解锁大门，魔法师需要将 $a$ 中的数字输出到另一个序列 $b$，并保证 $b$ 是非降序的。魔法师携带了 $k$ 根栈法杖作为解锁这扇神秘大门的工具。开始时，这些栈法杖都是空的，他可以使用三种栈法杖操作：

1. $(1, i)$: 从序列 $a$ 的末尾取出一个数字（栈的 pop 操作），并将它储存到第 $i$ 根栈法杖中（栈的 push 操作）。
2. $(2, i)$: 从第 $i$ 根栈法杖中取出最后一个储存的数字（栈的 pop 操作），并将其添加到输出序列 $b$ 的末尾（栈的 push 操作）。
3. $(3, i, j)$: 从第 $i$ 根栈法杖中取出最后一个储存的数字（栈的 pop 操作），并将其添加给第 $j$ 根栈法杖（栈的 push 操作）。

注意，魔法师不能直接将序列 $a$ 的末尾数字添加到输出序列 $b$ 中。年轻的魔法师深思熟虑后，意识到只要他手中的栈法杖数量 $k$ 大于等于序列 $a$ 的总数 $n$，他就一定能够解锁大门。

魔法师想知道，解锁大门所需的最少栈法杖数量 $k$ 是多少，并且设计一个巧妙的法杖操作方案，以确保输出序列 $b$ 是按非降序排列的。

需要找出完成解锁大门所需的最少栈法杖数量 $k$，并且设计一个巧妙的栈法杖操作方案，以确保输出序列 b 是按非降序排列的。

输入格式

第一行1个整数 $T$，代表有 $T$ 组数据

每组数据的第一行1个整数 $n$，代表序列长度

第二行 $n$ 个正整数 $a[i]$，代表序列中的元素

输出格式

对于每组数据，首先输出一行一个整数 $k$ 代表最少需要 $k$ 根栈法杖

第二行输出一个整数 $m$ 代表操作的次数

接下来 $m$ 行，你需要按以下格式输出操作方案：

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

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

请注意本题的输出量较大，请使用快速的输出方式

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$ 本体开放spj，你只需要输出答案符合要求的任意一种即可