시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)176545037.037%

문제

$1$부터 $N$까지의 정수를 하나씩 원소로 가지는 수열 $A_1,A_2,\cdots,A_N$이 주어진다.

다음과 같은 두 가지 연산을 최소 $1$번, 최대 $4$번 사용해서 수열의 모든 원소를 동일하게 만들어 보자.

  • $1 \:i$: $A_i$와 $A_{i+1}$를 바꾼다. $(1\leq i < N)$
  • $2 \:i \:j$: $i\leq k \leq j$인 모든 정수 $k$에 대해 $A_k$를 다음과 같이 바꾼다. $(1\leq i \leq j \leq N)$
    • $A_k > \max(A_i,A_j)$라면 $A_k$를 $\min(A_i,A_j)$로 바꾼다.
    • $A_k<\min(A_i,A_j)$라면 $A_k$를 $\max(A_i,A_j)$로 바꾼다.

입력

첫째 줄에 수열의 길이를 나타내는 정수 $N$이 주어진다. $(3\leq N \leq 300 \,000)$

둘째 줄에 정수로 이루어진 수열 $A_1,A_2,\cdots,A_N$이 공백으로 구분되어 주어진다. $(1\leq A_i \leq N)$

출력

$1$번 이상, $4$번 이하의 연산 안에 수열의 모든 원소를 동일하게 만드는 연산이 존재하는 경우, 첫째 줄에 연산의 사용 횟수를 나타내는 정수 $M(1\leq M \leq 4)$을 출력한다.

둘째 줄부터 $M$개의 줄에 걸쳐 사용한 연산을 사용한 순서대로 문제에서 명시한 형식으로 한 줄에 하나씩 출력한다.

수열의 모든 원소를 동일하게 만드는 연산이 존재하지 않거나, $1$번 이상 $4$번 이하의 연산 안에 동일하게 만들 수 있는 방법이 없는 경우, $-1$을 출력한다.

예제 입력 1

3
1 3 2

예제 출력 1

3
2 1 3
1 2
2 1 3

위 예제의 연산은 아래와 같은 과정으로 이루어진다.

  • $2\:1\:3$: $A_2 > \max(A_1,A_3)$이므로, $A_2$는 $\min(A_1,A_3)$인 $1$로 바뀌어 수열은 $[1,1,2]$로 바뀌게 된다.
  • $1\:2$: $A_2$와 $A_3$를 바꾸어 수열은 $[1,2,1]$로 바뀌게 된다.
  • $2\:1\:3$: $A_2> \max(A_1,A_3)$이므로, $A_2$는 $\min(A_1,A_3)$인 $1$로 바뀌어 수열은 $[1,1,1]$로 바뀌게 된다.

예제 입력 2

4
2 1 4 3

예제 출력 2

4
2 2 4
1 1
1 3
2 1 4