P15810 [JOI 2013 Final] Bubble Sort / Bubble Sort

**Bubble sort** is an algorithm for sorting a sequence. Suppose we want to sort an array $A$ of length $N$ in ascending order. Bubble sort checks two adjacent numbers, and if their order is incorrect, it swaps them. This process is done by scanning the array from front to back. That is, if there exists a position with $A_i > A_{i+1}$, then swap these two numbers, and perform this check once for each $i$ in the order $i = 1, 2, \dots, N-1$; this is called one scan. It is known that repeating such scans $N-1$ times will sort the array in ascending order. The **number of swaps in bubble sort** for the array $A$ means the number of integer swaps that occur when applying the above algorithm to $A$. (Known bubble sort algorithms and their implementations may differ slightly in loop order, range, termination conditions, etc. However, it is known that when applied to the same array, the number of integer swaps does not change because of these differences.) For example, the following program is a function written in C that sorts an integer array $a$ of length $n$ using bubble sort. ```cpp 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 one integer swap */ int x = a[j]; a[j] = a[j + 1]; a[j + 1] = x; } } } } ``` ### Task You are given a sequence $A$ of length $N$. Suppose we obtain a new sequence $A'$ by swapping two integers at arbitrary positions in $A$ exactly once. Write a program to find the minimum possible number of swaps in bubble sort for the sequence $A'$. (Note that the two integers swapped at the beginning do not have to be adjacent.)

Read the following data from standard input. - The first line contains an integer $N$. $N$ is the length of the sequence $A$. - In the next $N$ lines, the $i$-th line ($1 \leq i \leq N$) contains an integer $A_i$. This represents the $i$-th integer of the sequence $A$.

Output one line to standard output containing one integer, which is the minimum possible number of swaps in bubble sort for the sequence $A'$.

### Sample Explanation 1 If you swap $10$ at the beginning of the sequence $A$ with $1$ at the end, then the sequence $A'$ becomes a sorted sequence, and its number of swaps in bubble sort is $0$. ### Sample Explanation 2 If you swap the third number $7$ in the sequence $A$ with the last number $5$, then $A'$ becomes $3, 1, 5, 9, 7$. The number of swaps in bubble sort for $A'$ is $2$. ### Sample Explanation 3 Even if the sequence $A$ is already sorted at the beginning, you still must perform one swap when constructing $A'$. ### Constraints $1 \leq N \leq 100\,000$ the length of the sequence $A$ $1 \leq A_i \leq 1\,000\,000\,000$ the value of the numbers in the sequence $A$ ### Scoring In the testdata for scoring, the part worth 10% satisfies $N \leq 1000$, and for any $i, j$ ($1 \leq i < j \leq N$), we have $A_i \neq A_j$. In the testdata for scoring, the part worth 30% satisfies $N \leq 5000$, and for any $i, j$ ($1 \leq i < j \leq N$), we have $A_i \neq A_j$. In the testdata for scoring, the part worth 80% satisfies that for any $i, j$ ($1 \leq i < j \leq N$), we have $A_i \neq A_j$. Translated by ChatGPT 5