## DMOPC '18 Contest 1 P3 - Sorting

View as PDF

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Bob has a permutation of the integers . Bob has recently learned how to sort but he only knows one operation. A shift operation is defined as a sequence of distinct indices, . After the indices are chosen, the element at moves to , the element at moves to , and so on. The element at moves to . Bob does not know how to sort efficiently yet, so please tell him how to sort the permutation in increasing order using the minimum number of shift operations. If there are multiple best solutions you may output any.

#### Constraints

forms a permutation.

You will receive full points in this subtask as long as the shift operations correctly sort the permutation within operations.

For this subtask, it does not need to be sorted in the minimal number of shift operations.

Suppose is the maximum number of shift operations used in any test case of this subtask. Then:

For this subtask, it does not need to be sorted in the minimal number of shift operations.

You will receive full points in this subtask only if you sort the permutation in the minimal number of shift operations possible.

#### Input Specification

The first line contains one integer, .
The second line contains space-separated integers, , the permutation.

#### Output Specification

On the first line output , the number of shift operations needed to sort the permutation.
On the next lines, output followed by space-separated distinct integers describing the indices of the shift operation.
Failure to follow output specifications will result in a Wrong Answer verdict.

#### Sample Input 1

6
1 4 2 3 5 6

#### Sample Output 1

1
3 2 4 3

#### Sample Input 2

4
2 1 4 3

#### Sample Output 2

2
2 1 2
2 3 4