#P11474. [2023省队模拟]樱花抄

[2023省队模拟]樱花抄

题目描述

远野贵树给明里写了一封信,准备在见面的时候送给明里。然而写信时因为过于深情与激动,并没有一遍组织好自己的语言。句子的顺序有些混乱。

具体地,贵树的信件中有 nn 段话。现在贵树重审信件,将他的每段话都定下了一个权值,第 ii 段话的权值为 aia_i 。贵树希望重新调整段落的顺序,使得其权值为一个不降序列。

信件太长了,贵树没有时间重新誊写一遍。幸运的是信纸有特殊功能,贵树可以固定某段话,并将位于其前面的段落和后面的段落分别翻转。然而时间有限,贵树最多只能进行这样的操作 3×1053 \times 10^5 次。他希望你能帮他找到一个符合限制的操作方式,给他信中的话按权值排序。

因为你不是新海诚,所以你需要帮助所有时间线的贵树解决这个问题。

输入格式

第一行一个正整数 TT 表示时间线个数。 随后对于每条时间线,第一行输入一个正整数 nn ,表示贵树信件的话的段数。 第二行输入 nn 个正整数,第 ii 个数表示第 ii 段话的权值 aia_i 。

输出格式

对于每条时间线,输出一行或两行。 若不可能在 3×1053 \times 10^5 次操作内完成,输出一行一个数 −1-1 。 否则输出两行,第一行一个非负整数 kk 表示操作的次数,第二行 kk 个正整数, 表示每次操作中固定的段落是第几段。若有多种方案,输出任意一个即可。

数据范围

对于所有数据, 1≤n≤105,1≤ai≤n,1≤T≤51 \le n \le 10^5 , 1 \le a_i \le n, 1 \le T \le 5 。

子任务编号 依赖子任务 n≤n \le 分值
11 88 1010
22 11 1616
33 22 8080
44 33 300300
55 44 400400
66 55 20002000
77 66 2500025000
88 77 5000050000
99 88 7500075000
1010 99 10510^5

输入样例 1

2
6
1 4 3 5 3 2
6
6 5 4 3 2 1

输出样例 1

5
5 3 6 2 4
-1

样例解释

对于第一条时间线,其每段话的权值序列为 [1,4,3,5,3,2][1 , 4 , 3 , 5 , 3 , 2] 。

首先对第五段话操作,变为 [5,3,4,1,3,2][5 , 3 , 4 , 1 , 3 , 2] 。

然后对第三段话操作,变为 [3,5,4,2,3,1][3 , 5 , 4 , 2 , 3 , 1] 。

然后对第六段话操作,变为 [3,2,4,5,3,1][3 , 2 , 4 , 5 , 3 , 1] 。

然后对第二段话操作,变为 [3,2,1,3,5,4][3 , 2 , 1 , 3 , 5 , 4] 。

最后对第四段话操作,变为 [1,2,3,3,4,5][1 , 2 , 3 , 3 , 4 , 5] 。