[PFOI Round1] Two Subsegments

有 $T$ 组询问，每组询问给出一个长为 $n$ 的序列 $a$，保证 $a$ 是 $1\sim n$ 的排列。 你可以选择一个数 $x$，然后你每次可以将一段长为 $x+1$ 或一段长为 $x-1$ 的序列在原序列中前移或后移 $x$ 位，将经过的部分移到空出来的地方。 请在 $80\times n$ 次内将 $a$ 排成升序。 ## Input 第一行一个正整数 $T$。 接下来 $2 \times T$ 行，每两行代表一组询问。 对于每组询问，格式为：先一行一个正整数 $n$，接下来一行 $n$ 个正整数，代表 $a_1,\ldots,a_n$。 ## Output 输出共 $T$ 组。 一组询问如果无解，仅输出一个 $-1$。 如果有解，则输出共 $m+2$ 行： 前两行每行一个数，分别是 $x,m$，其中 $m$ 表示操作次数，$x$ 如题意。 接下来 $m$ 行，每行三个数，第一个数表示方向（向左是 $0$，向右是 $1$），接下来两个数 $l,r$ 代表平移区间的左、右端点。 你的方案需要保证： - $2\leq x\leq n$，$0\leq m\leq 80n$； - 对每一次操作，有： - $1\leq l\leq r\leq n$； - $r-l+1=x-1$ 或 $r-l+1=x+1$； - 右移时 $r\leq n-x$，左移时 $l\geq x+1$。 本题采用 $\text{SPJ}$，只要调换操作正确或正确判断无解即可给分。 [samples] ## Background >洛谷知名网红，€€£官方团队团主 [€€£](https://www.luogu.com.cn/user/559616) 同志，因联合省选寄，医院抢救无效，于 4 月 17 日 g 了。 > [€€£](https://www.luogu.com.cn/user/559616) 是知名洛谷人，2021年加入洛谷，同年成立 €€£ 官方团队。在他在位期间勤勤恳恳，认真整活，发奋出题，为整活革命化、现代化、正规化建设作出了贡献。 对于 [€€£](https://www.luogu.com.cn/user/559616) 的退役，[Uvocde](https://www.luogu.com.cn/user/111084) 深感悲痛。这时，他想起了 [€€£](https://www.luogu.com.cn/user/559616) 对构造的深爱，于是便出了这道题来缅怀 [€€£](https://www.luogu.com.cn/user/559616)。 ## Note 【样例解释】 对于 $2\ 1\ 4\ 7\ 6\ 5\ 3$ 这组样例： $x$ 取 $3$，共进行 $4$ 次操作： 0. **2 1 4 7** 6 5 3，向右平移； 1. 6 **5 3** 2 1 4 7，向右平移； 2. **6 2** 1 4 5 3 7，向右平移； 3. 1 4 5 6 **2 3** 7，向左平移； 4. 1 2 3 4 5 6 7，排序完成。 --- 【数据范围】 对于 $100\%$ 的数据，$1\le T\le10^4,\ 2\le n\le 10^4,\ \sum n\le10^4$，**保证排列在所有排列中等概率随机**。 | $\text{Subtasks}$ | 测试点数 | 数据范围 |分值 | | :-----------: | :-----------: | :-----------: | :-----------: | | $\text{Subtask0}$ | $1$ | $n\leq 5$ | $\text{2pts}$ | | $\text{Subtask1}$ | $7$ | $n\leq 50$ |$\text{7pts}$ | | $\text{Subtask2}$ | $9$ | $n\leq 10^3$ |$\text{27pts}$ | | $\text{Subtask3}$ | $14$ | $n\leq 5\times 10^3$ |$\text{27pts}$ | | $\text{Subtask4}$ | $9$ | $n\leq 10^4$ | $\text{37pts}$ |