Problem Statement

Bubble sort is one of the algorithms for sorting a sequence. Suppose we want to sort a sequence $A$ of length $N$ in ascending order. Bubble sort swaps the positions of $2$ adjacent numbers whenever their relative order is inverted. A single pass consists of scanning the sequence from front to back and swapping those $2$ numbers whenever $A_i > A_{i+1}$ for $i = 1, 2, \dots, N - 1$ in this order. It is known that repeating this pass $N - 1$ times sorts the sequence in ascending order.

The number of swaps by bubble sort on a sequence $A$ is the number of times integers are swapped when the above algorithm is applied to the sequence $A$. (Although algorithms and implementations known as bubble sort may have minor differences in loop order, ranges, and termination conditions, it is known that the number of integer swaps when applied to the same sequence does not change due to 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.

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

Task

Given a sequence $A$ of length $N$, suppose we create a sequence $A'$ by swapping $2$ integers at arbitrary positions in the sequence $A$ exactly $1$ time. Write a program to find the minimum possible number of swaps by bubble sort on the sequence $A'$. (Note that the $2$ integers swapped initially do not necessarily have to be adjacent.)

Constraints

• $1 \le N \le 100000$: the length of sequence $A$.
• $1 \le A_i \le 1000000000$: the magnitude of the numbers in sequence $A$.

Input

Read the following data from Standard Input:

• On the $1$-st line, an integer $N$ is written. $N$ represents the length of sequence $A$.
• On the $i$-th line ($1 \le i \le N$) of the following $N$ lines, an integer $A_i$ is written. This represents the $i$-th integer of sequence $A$.

Output

Print an integer representing the minimum possible number of swaps by bubble sort on the sequence $A'$ in $1$ line to Standard Output.

Grading Criteria

• For $10\%$ of the total score, $N \le 1000$, and $A_i \ne A_j$ holds for any $i, j$ ($1 \le i < j \le N$).
• For $30\%$ of the total score, $N \le 5000$, and $A_i \ne A_j$ holds for any $i, j$ ($1 \le i < j \le N$).
• For $80\%$ of the total score, $A_i \ne A_j$ holds for any $i, j$ ($1 \le i < j \le N$).

Sample

Sample Input 1

5
10
3
6
8
1

Sample Output 1

0

If we swap the first $10$ and the last $1$ of sequence $A$, the sequence $A'$ becomes a sorted sequence, and the number of swaps in bubble sort is $0$.

Sample Input 2

5
3
1
7
9
5

Sample Output 2

2

By swapping the $3$-rd element $7$ and the last element $5$ of sequence $A$, the sequence $A'$ becomes $3, 1, 5, 9, 7$. The number of swaps by bubble sort on $A'$ is $2$.

Sample Input 3

3
1
2
3

Sample Output 3

1

Even if sequence $A$ is already sorted from the beginning, a swap must be performed when creating sequence $A'$.