Problem Description

Bubble sort is one of the algorithms for sorting a sequence. Suppose you want to sort a sequence of length $N$ named $A$ in ascending order. Bubble sort works by swapping adjacent elements if they are out of order. This is done while traversing the sequence from the beginning. Specifically, for each $i = 1, 2, \ldots, N - 1$, if $A_i > A_{i + 1}$, these two numbers are swapped. This traversal is performed $N - 1$ times, and it is known that this process can sort the sequence in ascending order.

The number of swaps in bubble sort for a sequence $A$ is the number of times integers are swapped when the above algorithm is applied to the sequence $A$. (There may be slight differences in the bubble sort algorithm and its implementation, such as the order and range of loops, and termination conditions. However, it is known that the number of swaps does not change due to these differences when applied to the same sequence.)

For example, the following program is a function written in C language to sort an array of integers a of length n using bubble sort.

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;
      }
    }
  }
}

Input Format

Read the following data from standard input:

• The first line contains an integer $N$, which represents the length of the sequence $A$.
• The next $N$ lines contain an integer $A_i$ each, which represents the $i$-th integer in the sequence $A$.

Output Format

Output the minimum number of swaps in bubble sort for the sequence $A'$ to standard output in one line.

Sample Input and Output

Sample Input #1

5
10
3
6
8
1

Sample Output #1

0

Sample Input #2

5
3
1
7
9
5

Sample Output #2

2

Sample Input #3

3
1
2
3

Sample Output #3

1

Notes/Hints

Task

Given a sequence $A$ of length $N$, create a sequence $A'$ by swapping any two integers in the sequence $A$ exactly once. Write a program to find the minimum number of swaps in bubble sort for the sequence $A'$. (Note that the two integers to be swapped do not necessarily have to be adjacent.)

Constraints

$2 \leq N \leq 100,000$ - Length of sequence $A$
$1 \leq A_i \leq 1,000,000,000$ - Size of the numbers in sequence $A$ (Note) The constraints were adjusted during the migration of the past problem.

Grading Criteria

For 10% of the scoring data, $N \leq 1,000$ is satisfied, and for any $i, j$ ($1 \leq i < j \leq N$), $A_i \neq A_j$ is satisfied.

For 30% of the scoring data, $N \leq 5,000$ is satisfied, and for any $i, j$ ($1 \leq i < j \leq N$), $A_i \neq A_j$ is satisfied.

For 80% of the scoring data, for any $i, j$ ($1 \leq i < j \leq N$), $A_i \neq A_j$ is satisfied.

Sample Explanation 1

By swapping the first $10$ and the last $1$ in the sequence $A$, the sequence $A'$ becomes sorted, and the number of swaps in bubble sort is $0$.

Sample Explanation 2

By swapping the third $7$ and the last $5$ in the sequence $A$, the sequence $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, you must perform a swap to create the sequence $A'$.

见题面 Input 部分

见题面 Output 部分