시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 25 8 7 58.333%

문제

버블 정렬은 다음과 같은 의사 코드를 가지는 가장 간단한 정렬 방법 중 하나이다.

void bubble_sort(int *a, int n) {
    int i, j;
    for (i = 0; i < n - 1; ++i) {
        for (j = 0; j < n - 1; ++j) {
            if (a[j] > a[j + 1]) {
                /* 순서가 틀린 쌍이라면, 두 쌍을 교환한다. */ 
                /* 이 때 두 쌍의 교환 횟수는 1 증가한다. */
                int x = a[j];
                a[j] = a[j + 1];
                a[j + 1] = x;
            }
        }
    }
}

길이 n인 배열 A에 대해서 A*를 정의하고자 한다. A*는 배열 A의 i번째 원소와 j번째 원소를 한번만 바꿔놓은 배열이다. (1 <= i < j <= n).

모든 배열 A* 중, 교환 횟수가 최소인 배열 A*의 교환 횟수를 출력하라.

입력

첫번째 줄에 정수 N이 주어지며, 이후 N개의 줄에 배열 A가 A1... AN 순서로 주어진다.

  • 1 <= N <= 100,000
  • 1 <= Ai <= 1,000,000,000

출력

배열 A* 중 교환 횟수가 최소인 배열의 교환 횟수를 출력한다.

예제 입력

5
10
3
6
8
1

예제 출력

0

힌트

1과 10을 바꾸면 {1,3,6,8,10} 으로 정렬된 형태가 완성되기에 최솟값은 0이다.

출처

Olympiad > 일본정보올림피아드 > JOI 2013 5번