Japan Alumni Group Summer Camp 2015 Day 2

I - ツインリバース


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

Problem Statement

要素数 N の配列 A が与えられる。ただし、A(1,\ 2,\ ...,\ N) の順列である。

次の操作を 0 回以上 10,000 回以下の任意の回数行い、A(1,\ 2,\ ...,\ N) へソートしたい。

  • 整数 i (1\leq i\leq N) を 1 つ選び、区間 A[1,\ i-1] の要素を逆順にし、区間 A[i+1,\ N] の要素を逆順にする。

ただし、区間 A[l,\ r] とは Al,\ l+1,\ ...,\ r 番目の位置のことである。

A(1,\ 2,\ ...,\ N) へソートできるか判定せよ。ソートできるならば、操作の例を一つ出力せよ。

Constraints

  • 1\leq N\leq 3,000
  • A(1,\ 2,\ ...,\ N) の順列である。

Input Format

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 ... A_N

Output Format

A(1,\ 2,\ ...,\ N) へソートできないならば、-1 とだけ一行に出力せよ。

ソートできるならば、操作の例を一つ次のように出力せよ。

  • 1 行目には、操作の回数を表す整数 M (0\leq M\leq10,000) を出力せよ。
  • 2 行目からの M 行のうち k 行目には、k 回目の操作で選ぶ整数 i (1\leq i\leq N) を出力せよ。

Sample Input 1

5
5 1 4 2 3

Sample Output 1

2
3
1

例えば、次のように 2 回の操作を行えばよい。

  • i=3 を選ぶと (5,\ 1,\ 4,\ 2,\ 3)(1,\ 5,\ 4,\ 3,\ 2)
  • i=1 を選ぶと (1,\ 5,\ 4,\ 3,\ 2)(1,\ 2,\ 3,\ 4,\ 5)

Sample Input 2

2
2 1

Sample Output 2

-1

Sample Input 3

3
1 2 3

Sample Output 3

0

Submit提出する