리버스 정렬

길이 $N$의 순열 $P$가 있다. 당신은 한 연산에서 다음과 같은 연산을 최대 $10\,000$회 할 수 있다.

• $1 \leq l \leq r \leq N$인 $l$과 $r$을 고른다. 그 후 $P$에서 $l$부터 $r$까지의 부분 수열의 순서를 반대로 뒤집는다. 이 연산의 비용은 $(r-l) \operatorname{mod} 2$ 이다.

예를 들어 $[2,1,4,3,5]$에서 $l=2, r=4$인 연산을 사용한다면, $[2,\underline{3},\underline{4},\underline{1},5]$가 된다.

연산을 최대 $10\,000$번만 하여 순열 $P$를 오름차순으로 정렬하는 방법을 구해보자. 가능한 방법이 여러 가지라면, 사용한 연산의 비용의 합이 최소인 방법을 구해보자.

첫째 줄에 $N$이 주어진다. $(1 \leq N \leq 5\,000)$

둘째 줄에 $P_1, P_2, \cdots, P_N$가 공백으로 구분되어 주어진다.

첫째 줄에 연산의 횟수 $Q$를 출력한다. $(0 \leq Q \leq 10\,000)$

다음 $Q$개의 줄에 $i$번째 연산 $l_i$와 $r_i$를 공백으로 구분하여 출력한다. $(1 \leq l_i \leq r_i \leq N)$

순열 $P$를 최소한의 비용으로 정렬할 수 있는 방법이 여러 가지라면, 아무 방법이나 출력한다.

길이 $N$의 순열은 $1$부터 $N$까지의 수가 정확히 한 번 등장하는 수열을 말한다.

예를 들어, $[3,5,1,2,4]$와 $[1,3,2]$는 순열이지만, $[2,3,2]$또는 $[0]$은 순열이 아니다.

두 정수 $a$와 $b$에 대해 $a \operatorname{mod} b$는 $a$를 $b$로 나눈 나머지를 의미한다.

연산을 $10\,000$번 이하로 하여 주어진 순열을 항상 정렬할 수 있음을 보일 수 있다.