27233번 - 카드 플러리쉬 스페셜 저지

문제

주원이는 세계적인 마술사로부터 카드를 다루는 손기술을 배우고 있다. 주원이는 기술 연습을 위해 $N$장의 카드로 구성된 카드 덱을 샀다. 카드에는 1ドル$번부터 $N$번까지의 번호가 붙어 있으며, 덱의 위에서부터 오름차순으로 정렬되어 있다.

주원이는 오늘 한 손으로 카드를 섞는 기술 두 가지를 배웠다.

• 찰리어 컷: 카드를 연속한 두 묶음으로 나눈 뒤, 두 묶음의 순서를 뒤집는다.
• 트리플 컷: 카드를 연속한 세 묶음으로 나눈 뒤, 세 묶음의 순서를 뒤집는다.

각 묶음의 크기는 주원이가 원하는 대로 정할 수 있다. 주원이의 손은 누구보다도 정확하기 때문에, 카드를 정확히 원하는 크기의 묶음으로 나눌 수 있다. 단, 각 카드 묶음에는 반드시 하나 이상의 카드가 포함되어야 한다.

예시로 6ドル$장의 카드를 가지고 트리플 컷을 하는 과정을 살펴보자. 처음에는 덱의 맨 위에서부터 $(1,2,3,4,5,6)$번 순서대로 카드가 정렬되어 있다. 카드를 크기 2,1,3ドル$의 묶음으로 나눈다면 각 묶음에 들어 있는 카드 번호는 $(1,2) ,(3) ,(4,5,6)$과 같다. 세 묶음의 순서를 뒤집으면 $(4,5,6) ,(3) ,(1,2)$가 된다. 이 순서로 묶음을 합치면 최종적인 카드 순서는 $(4,5,6,3,1,2)$번이 된다.

주원이는 두 가지 손기술을 최대 $N-1$번 사용해서 덱을 원하는 순서로 섞으려고 한다. 덱을 원하는 순서로 만들 수 있는지 판별하고, 가능하다면 그 방법을 출력하시오.

입력

첫 번째 줄에 카드의 수 $N$이 주어진다.

두 번째 줄에 총 $N$개의 카드 번호가 주어진다. 이는 주원이가 최종적으로 만들고 싶어하는 카드의 순서를 나타낸다.

출력

만약 주원이가 손기술을 최대 $N-1$번 사용하여 덱을 원하는 순서로 섞을 수 없으면, 첫 번째 줄에 $-1$을 출력한다.

만약 주원이가 손기술을 최대 $N-1$번 사용하여 덱을 원하는 순서로 섞을 수 있으면, 첫 번째 줄에 주원이가 사용한 손기술의 횟수 $K$를 출력하고 다음 $K$개 줄에 걸쳐 아래 형식으로 그 과정을 순서대로 출력한다. $(0\le K\le N-1)$

• 2 a: 위에서부터 $[1,a]$번째 카드 묶음과 $[a+1,N]$번째 카드 묶음으로 나누는 찰리어 컷을 나타낸다. $(1\le a<N)$
• 3 a b: 위에서부터 $[1,a]$번째 카드 묶음, $[a+1,b]$번째 카드 묶음, $[b+1,N]$번째 카드 묶음으로 나누는 트리플 컷을 나타낸다. $(1\le a<b<N)$

손기술을 사용한 횟수가 최소일 필요는 없으며, 답이 여러 가지인 경우 아무거나 하나 출력한다.

제한

• 2ドル\le N\le 3\ 000$
• 주어지는 카드 번호는 1ドル$ 이상 $N$ 이하의 서로 다른 수이다.

힌트