당신에게 N명 선수들에 대한 koi4u 모의고사 성적이 있다. 당신은 그 성적들을 내림차순으로 정렬을 해야 한다.

불운하게도, N명 선수들에 대한 성적을 가지고 있는 자료구조가 한 종류의 작업 밖에 하질 못한다. 그 작업은 다른 선수들의 상대적 순서에 영향을 안주면서 i번에 위치해 있는 선수의 위치를 j번으로 바꾸는 작업이다. 즉, i > j일 때 j~i-1에 위치해 있는 선수들의 위치 값은 1씩 증가하고 i < j일 때 i+1~j에 위치해 있는 선수들의 위치 값은 1씩 감소한다.

이 작업은 움직일 선수를 찾는데 i번의 연산, 그리고 그 선수를 j의 위치로 옮기는데 j번의 연산이 필요하다. 따라서 한번의 작업에 i+j의 비용이 드는 것이다. 위치 값은 1 부터 시작해 연속 적이다.

어떻게 하면 최소의 비용으로 내림차순 정렬을 할 수 있을까? 그 방법을 구해보자.

입력

• 첫 줄에 정렬해야 하는 선수들의 수를 나타내는 자연수 N이 주어진다. (2 ≤ N ≤ 1,000)
• 다음 N줄에 각 선수들의 점수를 나타내는 정수 Si가 주어진다. (0 ≤ Si ≤ 1,000,000)
  각 선수들의 점수는 서로 다릅니다.

출력

입출력 예

입력

5
20
30
5
15
10
 
출력 
 
2
2 1
3 5
 

채점

출처:koi4u 2011 2차 모의고사 3 번