30623번 - 순열과 연산 스페셜 저지

문제

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$을 출력한다.

제한

힌트