시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB669712.281%

문제

You are given an array of n positive integers a1, a2, . . . , an. You can perform the following operation any number of times: select several distinct indices i1, i2, . . . , ik (1 ≤ ij ≤ n) and move the number standing at the position i1 to the position i2, the number at the position i2 to the position i3, . . . , the number at the position ik to the position i1. In other words, the operation cyclically shifts elements: i1 → i2 → . . . ik → i1.

For example, if you have n = 4, an array a1 = 10, a2 = 20, a3 = 30, a4 = 40, and you choose three indices i1 = 2, i2 = 3, i3 = 4, then the resulting array would become a1 = 10, a2 = 40, a3 = 20, a4 = 30.

Your goal is to make the array sorted in non-decreasing order with 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.

입력

The first line of the input contains two integers n and s (1 ≤ n ≤ 200 000, 0 ≤ s ≤ 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 a1, a2, . . . , an—elements of the array (1 ≤ ai ≤ 109).

출력

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 2q 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 ≤ k ≤ n)—the length of the cycle (that is, the number of selected indices). The next line should contain k distinct integers i1, i2, . . . , ik (1 ≤ ij ≤ 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.

서브태스크

번호배점제한
15

n, s ≤ 2 and all elements of the array are either 1 or 2

25

n ≤ 5

35

All elements of the array are either 1 or 2

410

Array contains numbers from 1 to n only, each number appears exactly once, s = 2 · n

510

Array contains numbers from 1 to n only, each number appears exactly once, n ≤ 1000

615

Array contains numbers from 1 to n only, each number appears exactly once

715

s = 2 · n

815

n ≤ 1000

920

No additional constraints

예제 입력 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

예제 입력 4

6 9
6 5 4 3 2 1

예제 출력 4

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

예제 입력 5

6 8
6 5 4 3 2 1

예제 출력 5

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

힌트

In the first example, it’s also possible to sort the array with two operations of total length 5: first apply the cycle 1 → 4 → 1 (of length 2), then apply the cycle 2 → 3 → t → 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 → 2 → 1 and 3 → 4 → 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.

Notice that examples 1 and 3 contain duplicate numbers, so they do not satisfy requirements for subtasks 4, 5 and 6. Examples 2, 4, and 5 satisfy requirements for subtasks 5 and 6.

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.