시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 12 3 3 37.500%

문제

상근이는 몇 달전에 대박의 꿈을 안고 아이폰 앱의 세계에 발을 들였다. 상근이는 게임을 하나 만들었는데, 이 게임에는 전체 사용자의 순위를 보여주는 기능이 있다. 상근이는 점수를 내림차순으로 정렬해 사용자의 순위를 보여주려고 한다.

사용자의 점수를 저장하는데 사용한 자료구조는 오직 연산 하나만 수행할 수 있다. 이 연산은 i번째 사용자를 j번째로 옮기는데, 다른 사용자의 상대적인 순서를 바꾸지 않는다.

예를 들어, i>j인 경우에 j와 i-1번 사이의 사용자의 순위는 1씩 증가한다. 반대로 i<j인 경우에는 i+1과 j 사이의 사용자의 순위가 1씩 감소한다.

연산을 한 번 사용할 때, 이동시킬 사용자를 찾는데 i단계, 이동할 위치를 찾는데 j단계가 필요하기 때문에, i번째 사용자를 j번째로 옮기는데 드는 비용은 i+j이다. 순위는 1부터 시작한다.

현재 자료구조에 저장된 점수가 주어졌을 때, 사용자를 내림차순으로 정렬하기 위해 필요한 비용의 최소값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 저장된 점수의 수 n (2 ≤ n ≤ 1000) 이 주어진다. 다음 줄에는 점수 si가 현재 자료구조에 저장되어 있는 순서대로 주어진다. (0 ≤ si ≤ 1,000,000) 두 점수가 같은 경우는 없다.

출력

첫째 줄에 점수를 내림차순으로 정렬하기 위해 필요한 이동 횟수를 출력한다. 다음 줄에는 각 이동을 순서대로 출력한다. i번째 점수를 j번째로 옮긴 경우에는 i j를 출력한다.

예제 입력

5
20
30
5
15
10

예제 출력

2
2 1
3 5

힌트

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2007 2번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: onjo0127