문제 설명

버블 소트란 수열을 정렬하는 알고리즘 중 하나이다. 길이가 $N$인 수열 $A$를 오름차순으로 정렬하고 싶다고 하자. 버블 소트는 인접한 $2$개의 수 중에서 대소 관계가 어긋난 것이 있으면 그 위치를 교환한다. 이를 수열의 앞에서부터 차례대로 주사하면서 수행한다. 즉, $A_i > A_{i+1}$인 곳이 있으면 그 $2$개의 수를 교환하는 것을 $i = 1, 2, \dots, N - 1$에 대하여 이 순서대로 수행하는 것이 1회의 주사이다. 이 주사를 $N - 1$회 반복함으로써 수열을 오름차순으로 정렬할 수 있음이 알려져 있다.

수열 $A$의 버블 소트에 의한 교환 횟수란, 수열 $A$에 위 알고리즘을 적용했을 때 정수의 교환이 이루어지는 횟수이다. (버블 소트로 알려진 알고리즘 및 구현에는 루프의 순서나 범위, 종료 조건 등 미세한 차이가 있는 경우가 있다. 단, 같은 수열에 적용했을 때의 정수 교환 횟수는 그러한 차이에 의해 변하지 않음이 알려져 있다.)

예를 들어, 아래 프로그램은 길이가 n인 정수 배열 a를 버블 소트로 정렬하는 함수를 C 언어로 기술한 것이다.

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]) {
        /* The following 3 lines correspond to 1 swap of integers */
        int x = a[j];
        a[j] = a[j + 1];
        a[j + 1] = x;
      }
    }
  }
}

과제

길이가 $N$인 수열 $A$가 주어진다. 수열 $A$의 임의의 위치에 있는 $2$개의 정수를 단 $1$번만 교환한 수열 $A'$을 만든다고 하자. 수열 $A'$의 버블 소트에 의한 교환 횟수의 최솟값을 구하는 프로그램을 작성하시오. (처음에 교환하는 $2$개의 정수는 반드시 인접해 있을 필요는 없다는 점에 주의하시오.)

제한

• $1 \le N \le 100000$: 수열 $A$의 길이.
• $1 \le A_i \le 1000000000$: 수열 $A$에 포함되는 수의 크기.

입력

표준 입력으로부터 다음 데이터를 읽어들여라.

• $1$번째 줄에는 정수 $N$이 적혀 있다. $N$은 수열 $A$의 길이를 나타낸다.
• 이어지는 $N$개의 줄 중 $i$번째 줄 ($1 \le i \le N$)에는 정수 $A_i$가 적혀 있다. 이는 수열 $A$의 $i$번째 정수를 나타낸다.

출력

표준 출력에 수열 $A'$의 버블 소트에 의한 교환 횟수의 최솟값을 나타내는 정수를 $1$줄로 출력하시오.

채점 기준

• 채점용 데이터 중 배점의 $10\%$에 대해서는 $N \le 1000$을 만족하며, 임의의 $i, j$ ($1 \le i < j \le N$)에 대해 $A_i \ne A_j$를 만족한다.
• 채점용 데이터 중 배점의 $30\%$에 대해서는 $N \le 5000$을 만족하며, 임의의 $i, j$ ($1 \le i < j \le N$)에 대해 $A_i \ne A_j$를 만족한다.
• 채점용 데이터 중 배점의 $80\%$에 대해서는 임의의 $i, j$ ($1 \le i < j \le N$)에 대해 $A_i \ne A_j$를 만족한다.

입출력 예제

입력 예제 1

5
10
3
6
8
1

출력 예제 1

0

수열 $A$의 처음 $10$과 마지막 $1$을 교환하기로 하면, 수열 $A'$은 정렬된 수열이 되어 버블 소트의 교환 횟수는 $0$이 된다.

입력 예제 2

5
3
1
7
9
5

출력 예제 2

2

수열 $A$의 $3$번째 수인 $7$과 마지막 수인 $5$를 교환함으로써 수열 $A'$은 $3, 1, 5, 9, 7$이 된다. $A'$의 버블 소트에 의한 교환 횟수는 $2$이다.

입력 예제 3

3
1
2
3

출력 예제 3

1

처음부터 수열 $A$가 정렬되어 있는 경우라도, 수열 $A'$을 만들 때 반드시 교환을 수행해야 한다.