시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 100 47 34 53.125%

문제

욱제는 카드 게임에서 1부터 N까지의 정수가 중복되지 않게 하나씩 적혀있는 N개의 카드를 배정 받았다. 욱제는 배정 받은 카드를 책상 위에 일렬로 배열했다. 하지만 결벽증이 있는 욱제는 카드가 아무 순서대로 배열되는 걸 참을 수 없었다!

욱제는 카드 배열을 벗어나지 않는 어떤 구간 [L, R](1 ≤ L < R ≤ N)을 정해서 이 구간을 통째로 뒤집는(reverse) 연산을 할 수 있다. 예를 들어, 배열 {1, 5, 10, 15, 20, 25}에서 [2, 5]를 뒤집으면 {1, 20, 15, 10, 5, 25}가 된다.

욱제의 결벽증을 최대한 해소하려면, 이러한 연산을 잘 수행해서 어떤 상태에 최대한 가깝게 만들어야 한다. 왼쪽부터 카드에 인덱스를 부여했을 때, i번째 카드에 정수 i가 가장 많이 적힌 상태가 바로 그 상태이다.

“왼쪽 문짝이 오른쪽 문짝보다 0.256mm 정도 더 기울었잖아?!?!?!?!?”

욱제의 결벽증이 극에 달하고 있다! 욱제를 위해 최대한 많은 카드를 최적의 상태로 만들어주자!

입력

첫째 줄에 카드 개수 N이 주어진다. (1 ≤ N ≤ 1,000)

둘째 줄에 초기의 카드 배열이 왼쪽부터 순서대로 주어진다.

출력

첫째 줄에 주어진 조건에 맞게 카드를 배열하기 위해 필요한 연산의 횟수 op를 출력한다. op는 N×N보다 작거나 같아야 한다.

이후 op개의 줄에 걸쳐 연산에 필요한 [L, R]쌍을 순서대로 출력한다. op가 0이라면 아무것도 출력하지 않는다. L과 R은 하나의 공백을 사이에 두고 출력한다.

예제 입력 1

5
2 1 5 4 3

예제 출력 1

2
3 5
1 2

예제 입력 2

5
5 2 1 4 3

예제 출력 2

2
1 3
3 5

예제 입력 3

1
1

예제 출력 3

0