给你一个 $$$n$$$ 正整数数组 $$$a_1, a_2, \dots, a_n$$$。您可以多次执行以下操作:选择多个不同的索引 $$$i_1, i_2, \dots, i_k$$$ ($$$1 \le i_j \le n$$$) 并将 $$$i_1$$$ 位置上的数字移动到 $$$i_2$$$ 位置,将 $$$i_2$$$ 位置上的数字移动到 $$$i_3$$$ 位置,...,将该位置上的数字移动$$$i_k$$$ 到位置 $$$i_1$$$。换句话说,该操作循环移位元素:$$$i_1 \to i_2 \to \ldots i_k \to i_1$$$。
例如,如果您有 $$$n=4$$$,数组 $$$a_1=10、a_2=20、a_3=30、a_4=40$$$,并且您选择三个索引 $$$i_1=2$$$、$$$i_2=1$$$、$$$i_3=4$$$,则生成的数组将变为$$$a_1=20,a_2=40,a_3=30,a_4=10$$$。
你的目标是用最少的操作次数使数组按非降序排序。附加约束是所有操作的循环长度总和应小于或等于数字 $$$s$$$。如果在满足该约束的同时无法对数组进行排序,您的解决方案也应该报告这一点。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$s$$$ ($$$1 \leq n \leq 200\,000$$$, $$$0 \leq s \leq 200\,000$$$) - 数组中的元素数量以及循环长度总和的上限。
下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ — 数组的元素 ($$$1 \leq a_i \leq 10^9$$$)。
输出
如果无法使用总长度不超过 $$$s$$$ 的循环对数组进行排序,请打印单个数字“-1”(为了清楚起见,使用引号)。
否则,打印单个数字 $$$q$$$ — 对数组进行排序所需的最少操作数。
在接下来的 $$$2 \cdot q$$$ 行中,按照应用于数组的顺序打印操作描述。第 $$$i$$$ 操作的描述从一行开始,其中包含一个整数 $$$k$$$ ($$$1 \le k \le n$$$)——循环的长度(即所选索引的数量)。下一行应包含 $$$k$$$ 不同的整数 $$$i_1, i_2, \dots, i_k$$$ ($$$1 \le i_j \le n$$$) — 循环的索引。
这些循环的长度总和应小于或等于 $$$s$$$,并且在应用这些 $$$q$$$ 操作后应对数组进行排序。
如果有多个可能的答案且最优 $$$q$$$,请打印其中任何一个。
示例
输入 #1
5 5 3 2 3 1 1
输出 #1
1 5 1 4 2 3 5
输入 #2
4 3 2 1 4 3
输出 #2
-1
输入 #3
2 0 2 2
输出 #3
0
注意
在第一个示例中,还可以使用总长度为 5 的两个操作对数组进行排序:首先应用循环 $$$1 \to 4 \to 1$$$ (长度为 2),然后应用循环 $$$2 \to 3 \to 5 \to 2$$$ (长度为 3)。但是,这将是错误的答案,因为您被要求使用尽可能少的操作数,在这种情况下为 1。
在第二个示例中,可以使用总长度为 4 的两个循环($$$1 \to 2 \to 1$$$ 和 $$$3 \to 4 \to 3$$$)对数组进行排序。然而,使用更短的周期是不可能实现相同的目的,而这是 $$$s=3$$$ 所要求的。
在第三个示例中,数组已经排序,因此不需要任何操作。空循环集的总长度被认为为零。