아드레날린 러시

앨리스의 친구는 레이싱 대회 Adrenaline Rush의 열렬한 팬이라 모든 경기를 빠짐없이 보려고 합니다. 이번에는 앨리스가 직접 경기를 봅니다. 친구가 중요한 장면을 놓치지 않도록 앨리스는 트랙에서 일어나는 일을 모두 기록하기로 했습니다.

경기가 시작되기 전 앨리스가 가장 먼저 눈여겨본 것은 차량 번호입니다. 모든 차량은 정해진 순서대로 출발선 앞에 줄을 섭니다. 출발선에 가장 가까운 차량의 번호는 $1$이고, 두 번째 차량은 $2$, 이런 식으로 마지막 차량 $n$까지 번호가 붙습니다. 편리하네, 라고 앨리스는 생각합니다.

경기는 "Three! Two! One! Go!"라는 카운트다운으로 시작합니다. 앨리스는 차량들이 원래 순서대로 출발하는 것을 확인합니다. 그러나 경기가 진행되면서 순서가 바뀝니다. 한 차량이 다른 차량을 추월할 때마다 두 차량은 트랙 위에서 자리를 맞바꾸고, 앨리스는 이를 기록합니다.

경기 중 앨리스는 특이한 점을 발견합니다. 어떤 차량도 같은 차량을 두 번 이상 추월하지 않습니다. 임의의 두 차량 $x$와 $y$ 사이에 일어나는 추월은 최대 두 번이며, "$x$가 $y$를 추월한다" 또는 "$y$가 $x$를 추월한다" 중 하나이거나 둘 다입니다.

경기가 끝나면 앨리스는 최종 순서 $c_1, c_2, \ldots, c_n$을 꼼꼼히 적습니다. 여기서 $c_1$은 우승한 차량입니다.

앨리스의 친구는 최종 순위에만 관심이 있어서 그 순서를 제외한 앨리스의 메모를 모두 버립니다. 하지만 앨리스는 궁금합니다. 앨리스가 관찰했을 수 있는 추월 기록의 최대 길이는 얼마일까요? 그 답을 찾아 주세요.

첫째 줄에 차량의 수 $n$($1 \le n \le 1000$)이 주어집니다.

둘째 줄에는 순열 $c_1, c_2, \ldots, c_n$($1 \le c_i \le n$, $c_i \ne c_j$)이 주어집니다. 이는 경기가 끝났을 때의 최종 순서입니다.

첫째 줄에 가능한 추월의 최대 횟수 $m$을 출력합니다.

이어지는 $m$개의 줄에는 두 정수 $x$와 $y$($1 \le x, y \le n$, $x \ne y$)를 출력합니다. 이는 차량 $x$가 차량 $y$를 추월했다는 뜻이며, 추월하는 순간 차량 $x$는 차량 $y$의 바로 뒤에 있었습니다. 추월은 실제로 일어난 순서대로 나열합니다.

모든 추월이 끝난 뒤 차량은 $c_1, c_2, \ldots, c_n$ 순서로 결승선에 도착해야 합니다. 어떤 차량 $x$도 같은 차량 $y$를 두 번 이상 추월해서는 안 됩니다. 최장 기록이 여러 가지라면 그중 아무것이나 출력해도 됩니다.