English · Original
Chinese · Translation
Formal · Original
You are given an array of $n$ positive integers $a_1, a_2, \dots, a_n$. You can perform the following operation any number of times: select several distinct indices $i_1, i_2, \dots, i_k$ ($1 \le i_j \le n$) and move the number standing at the position $i_1$ to the position $i_2$, the number at the position $i_2$ to the position $i_3$, ..., the number at the position $i_k$ to the position $i_1$. In other words, the operation cyclically shifts elements: $i_1 \to i_2 \to \ldots i_k \to i_1$.
For example, if you have $n=4$, an array $a_1=10, a_2=20, a_3=30, a_4=40$, and you choose three indices $i_1=2$, $i_2=1$, $i_3=4$, then the resulting array would become $a_1=20, a_2=40, a_3=30, a_4=10$.
Your goal is to make the array sorted in non-decreasing order with the minimum number of operations. The additional constraint is that the sum of cycle lengths over all operations should be less than or equal to a number $s$. If it's impossible to sort the array while satisfying that constraint, your solution should report that as well.
## Input
The first line of the input contains two integers $n$ and $s$ ($1 \leq n \leq 200\,000$, $0 \leq s \leq 200\,000$)—the number of elements in the array and the upper bound on the sum of cycle lengths.
The next line contains $n$ integers $a_1, a_2, \dots, a_n$—elements of the array ($1 \leq a_i \leq 10^9$).
## Output
If it's impossible to sort the array using cycles of total length not exceeding $s$, print a single number "_\-1_" (quotes for clarity).
Otherwise, print a single number $q$— the minimum number of operations required to sort the array.
On the next $2 \cdot q$ lines print descriptions of operations in the order they are applied to the array. The description of $i$\-th operation begins with a single line containing one integer $k$ ($1 \le k \le n$)—the length of the cycle (that is, the number of selected indices). The next line should contain $k$ distinct integers $i_1, i_2, \dots, i_k$ ($1 \le i_j \le n$)—the indices of the cycle.
The sum of lengths of these cycles should be less than or equal to $s$, and the array should be sorted after applying these $q$ operations.
If there are several possible answers with the optimal $q$, print any of them.
[samples]
## Note
In the first example, it's also possible to sort the array with two operations of total length 5: first apply the cycle $1 \to 4 \to 1$ (of length 2), then apply the cycle $2 \to 3 \to 5 \to 2$ (of length 3). However, it would be wrong answer as you're asked to use the minimal possible number of operations, which is 1 in that case.
In the second example, it's possible to the sort the array with two cycles of total length 4 ($1 \to 2 \to 1$ and $3 \to 4 \to 3$). However, it's impossible to achieve the same using shorter cycles, which is required by $s=3$.
In the third example, the array is already sorted, so no operations are needed. Total length of empty set of cycles is considered to be zero.
你被给定一个包含 $n$ 个正整数的数组 $a_1, a_2, dots.h, a_n$。你可以任意次执行以下操作：选择若干个互不相同的下标 $i_1, i_2, dots.h, i_k$（$1 lt.eq i_j lt.eq n$），并将位置 $i_1$ 上的数移动到位置 $i_2$，位置 $i_2$ 上的数移动到位置 $i_3$，……，位置 $i_k$ 上的数移动到位置 $i_1$。换句话说，该操作对元素进行循环移位：$i_1 arrow.r i_2 arrow.r dots.h i_k arrow.r 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 lt.eq n lt.eq 200 thin 000$, $0 lt.eq s lt.eq 200 thin 000$）——数组元素个数和循环长度总和的上限。
第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$——数组元素（$1 lt.eq a_i lt.eq 10^9$）。
如果无法使用总长度不超过 $s$ 的循环对数组排序，请输出单个数字 "_-1_"（引号仅用于清晰说明）。
否则，输出单个数字 $q$——将数组排序所需的最少操作次数。
接下来的 $2 dot.op q$ 行按应用顺序描述每个操作。第 $i$ 个操作的描述以一行开始，包含一个整数 $k$（$1 lt.eq k lt.eq n$）——循环的长度（即所选下标个数）。下一行应包含 $k$ 个互不相同的整数 $i_1, i_2, dots.h, i_k$（$1 lt.eq i_j lt.eq n$）——循环的下标。
这些循环的长度总和应不超过 $s$，且在应用这 $q$ 次操作后数组应为有序。
如果存在多个满足最优 $q$ 的答案，请输出任意一个。
在第一个例子中，也可以用两次操作（总长度为 5）对数组排序：先应用循环 $1 arrow.r 4 arrow.r 1$（长度为 2），再应用循环 $2 arrow.r 3 arrow.r 5 arrow.r 2$（长度为 3）。但这是错误答案，因为题目要求使用最少的操作次数，该情况下最少为 1 次。
在第二个例子中，可以用两个循环（总长度为 4：$1 arrow.r 2 arrow.r 1$ 和 $3 arrow.r 4 arrow.r 3$）对数组排序。但无法使用长度总和不超过 $s = 3$ 的更短循环达成相同效果。
在第三个例子中，数组已有序，因此无需任何操作。空循环集合的总长度视为 0。
## Input
输入的第一行包含两个整数 $n$ 和 $s$（$1 lt.eq n lt.eq 200 thin 000$, $0 lt.eq s lt.eq 200 thin 000$）——数组元素个数和循环长度总和的上限。第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$——数组元素（$1 lt.eq a_i lt.eq 10^9$）。
## Output
如果无法使用总长度不超过 $s$ 的循环对数组排序，请输出单个数字 "_-1_"（引号仅用于清晰说明）。否则，输出单个数字 $q$——将数组排序所需的最少操作次数。接下来的 $2 dot.op q$ 行按应用顺序描述每个操作。第 $i$ 个操作的描述以一行开始，包含一个整数 $k$（$1 lt.eq k lt.eq n$）——循环的长度（即所选下标个数）。下一行应包含 $k$ 个互不相同的整数 $i_1, i_2, dots.h, i_k$（$1 lt.eq i_j lt.eq n$）——循环的下标。这些循环的长度总和应不超过 $s$，且在应用这 $q$ 次操作后数组应为有序。如果存在多个满足最优 $q$ 的答案，请输出任意一个。
[samples]
## Note
在第一个例子中，也可以用两次操作（总长度为 5）对数组排序：先应用循环 $1 arrow.r 4 arrow.r 1$（长度为 2），再应用循环 $2 arrow.r 3 arrow.r 5 arrow.r 2$（长度为 3）。但这是错误答案，因为题目要求使用最少的操作次数，该情况下最少为 1 次。在第二个例子中，可以用两个循环（总长度为 4：$1 arrow.r 2 arrow.r 1$ 和 $3 arrow.r 4 arrow.r 3$）对数组排序。但无法使用长度总和不超过 $s = 3$ 的更短循环达成相同效果。在第三个例子中，数组已有序，因此无需任何操作。空循环集合的总长度视为 0。
**Definitions**
Let $ n, s \in \mathbb{Z} $ with $ 1 \le n \le 200{,}000 $, $ 0 \le s \le 200{,}000 $.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers.
Let $ B = (b_1, b_2, \dots, b_n) $ be the sorted version of $ A $ in non-decreasing order.
Define a permutation $ \pi \in S_n $ such that for each position $ i \in \{1, \dots, n\} $, the element $ a_i $ should move to position $ \pi(i) $ in the sorted array, i.e., $ a_i = b_{\pi(i)} $.
Assume indices are 1-based.
A *cycle operation* is a cyclic permutation of a subset of indices $ \{i_1, i_2, \dots, i_k\} $, where $ k \ge 1 $, such that:
$ i_1 \mapsto i_2, i_2 \mapsto i_3, \dots, i_k \mapsto i_1 $.
**Constraints**
1. The total sum of lengths of all applied cycle operations must satisfy $ \sum \text{len}(C_j) \le s $.
2. After applying all operations, the array must equal $ B $.
3. Each cycle operation must act on distinct indices and correspond to a cycle in the permutation $ \pi $.
**Objective**
Find the minimum number $ q $ of cycle operations such that:
- The composition of these cycles equals $ \pi $,
- The sum of the lengths of the cycles is $ \le s $.
If no such sequence of cycles exists, output $-1$.
Otherwise, output $ q $, followed by $ q $ cycle descriptions (each: length $ k $, then $ k $ indices).
**Note**: The minimal number of operations $ q $ is equal to the number of cycles in the cycle decomposition of $ \pi $, excluding fixed points (cycles of length 1).
Any cycle of length $ k \ge 2 $ must be applied as a single operation of length $ k $.
Fixed points (cycles of length 1) require no operation.
Thus, the total cycle length sum is $ \sum_{C \in \text{cycles of } \pi, |C| \ge 2} |C| $.
If this sum exceeds $ s $, output $-1$.
Otherwise, output $ q = \#\{C \in \text{cycles of } \pi : |C| \ge 2\} $, followed by the cycles.
API Response (JSON)
{
"problem": {
"name": "E. Cycle sort",
"description": {
"content": "You are given an array of $n$ positive integers $a_1, a_2, \\dots, a_n$. You can perform the following operation any number of times: select several distinct indices $i_1, i_2, \\dots, i_k$ ($1 \\le i_j ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF1012E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "You are given an array of $n$ positive integers $a_1, a_2, \\dots, a_n$. You can perform the following operation any number of times: select several distinct indices $i_1, i_2, \\dots, i_k$ ($1 \\le i_j ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "你被给定一个包含 $n$ 个正整数的数组 $a_1, a_2, dots.h, a_n$。你可以任意次执行以下操作：选择若干个互不相同的下标 $i_1, i_2, dots.h, i_k$（$1 lt.eq i_j lt.eq n$），并将位置 $i_1$ 上的数移动到位置 $i_2$，位置 $i_2$ 上的数移动到位置 $i_3$，……，位置 $i_k$ 上的数移动到位置 $i_1$。换句话说，...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, s \\in \\mathbb{Z} $ with $ 1 \\le n \\le 200{,}000 $, $ 0 \\le s \\le 200{,}000 $. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers. \nLet $ B = (b_1, b_2,...",
"is_translate": false,
"language": "Formal"
}
]
}