Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Cycle sort

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

Examples

Input

5 5

3 2 3 1 1

Output

1

5

1 4 2 3 5

Input

4 3

2 1 4 3

Output

-1

Input

2 0

2 2

Output

0

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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/16/2018 00:59:42 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|