시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 28 21 19 79.167%

문제

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

매장에는 $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)$

서브태스크

번호 배점 제한
1 20

$N \le 10$

2 25

$N \le 50$

3 55

추가 제한 조건이 없습니다.

예제 입력 1

5
1 2 3 4 5

예제 출력 1

0

예제 입력 2

5
1 3 2 5 4

예제 출력 2

2
2 3
4 5

채점 및 기타 정보

  • 예제는 채점하지 않는다.