21554번 - 마법의 돌 장난감 서브태스크스페셜 저지

폴리매스 왕국의 힘은 마법의 돌로부터 흘러나온다는 전설이 있습니다. 당신은 마법의 돌 장난감을 판매하는 친구의 부탁을 받아 가게 정리를 돕기로 했습니다.

매장에는 $N$개의 장난감이 있고, 이들의 크기는 $1$부터 $N$ 사이의 자연수로 서로 다릅니다. 당신은 이 장난감을 크기 순서로 정렬하려고 합니다. 즉, 왼쪽부터 크기가 차례로 $1, 2, \cdots, N$이 되도록 하려고 합니다. 당신은 이를 위해 몇 번의 ‘조작’을 할 수 있습니다. 한 번의 조작은 인접한 몇 개의 장난감을 골라, 순서를 뒤집는 일입니다. 예를 들어, 왼쪽부터 장난감들의 크기가 차례로 $1, 2, 5, 4, 3$인 상황에서 세 번째부터 다섯 번째 장난감에 ‘조작’을 하면, 장난감들의 크기는 차례로 $1, 2, 3, 4, 5$가 되며, 정렬이 완료됩니다.

장난감을 100회 이하의 ‘조작’으로 정렬할 수 있는지 판단하고, 정렬할 수 있다면 방법을 아무거나 찾는 프로그램을 작성하세요.

첫 줄에는 장난감의 수 $N$이 주어집니다. 둘째 줄에는 각 장난감의 크기를 나타내는 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 주어집니다. 각 수는 빈칸을 사이에 두고 주어집니다.

만약 100번 이하의 ‘조작’으로 장난감을 정렬하는 것이 불가능하다면, $-1$을 출력하고 프로그램을 종료합니다. 만약 장난감을 정렬하는 것이 가능하다면, 첫 줄에는 ‘조작’의 횟수 $Q$를 출력합니다. 둘째 줄부터 $Q$개의 줄에는 각 ‘조작’에서 영향을 받는 장난감의 왼쪽 끝 번호 $l_i$와 오른쪽 끝 번호 $r_i$를 출력합니다. 예를 들어, 왼쪽에서 세 번째 장난감부터 왼쪽에서 다섯 번째 장난감까지에 ‘조작’을 한다면, $3$ $5$를 출력합니다.

• $1 \le N \le 100$
• $1 \le A_i \le N$
• $i \neq j \Leftrightarrow A_i \neq A_j$

만약 정렬이 가능하다면, 출력은 아래 조건을 만족해야 합니다.

• $0 \le Q \le 100$
• $1 \le l_i \le r_i \le N$ $(1 \le i \le Q)$