Enunciado del problema

El ordenamiento de burbuja es uno de los algoritmos para ordenar una secuencia. Supongamos que queremos ordenar una secuencia $A$ de longitud $N$ en orden ascendente. El ordenamiento de burbuja intercambia las posiciones de $2$ números adyacentes si su relación de orden está invertida. Una pasada consiste en recorrer la secuencia de principio a fin e intercambiar esos $2$ números siempre que $A_i > A_{i+1}$ para $i = 1, 2, \dots, N - 1$ en este orden. Se sabe que al repetir esta pasada $N - 1$ veces se logra ordenar la secuencia en orden ascendente.

El número de intercambios mediante el ordenamiento de burbuja en una secuencia $A$ es la cantidad de veces que se intercambian enteros al aplicar el algoritmo anterior a la secuencia $A$. (Aunque los algoritmos e implementaciones conocidos como ordenamiento de burbuja pueden tener pequeñas diferencias en el orden de los bucles, los rangos y las condiciones de parada, se sabe que el número de intercambios de enteros al aplicarlos a la misma secuencia no varía debido a dichas diferencias).

Por ejemplo, el siguiente programa es una función escrita en lenguaje C que ordena un arreglo de enteros a de longitud n mediante el ordenamiento de burbuja.

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

Tarea

Se da una secuencia $A$ de longitud $N$. Supongamos que creamos una secuencia $A'$ intercambiando $2$ enteros en posiciones arbitrarias de la secuencia $A$ exactamente $1$ vez. Escribe un programa para encontrar el valor mínimo del número de intercambios mediante el ordenamiento de burbuja en la secuencia $A'$. (Ten en cuenta que los $2$ enteros que se intercambian inicialmente no tienen por qué ser adyacentes).

Restricciones

• $1 \le N \le 100000$: la longitud de la secuencia $A$.
• $1 \le A_i \le 1000000000$: el tamaño de los números incluidos en la secuencia $A$.

Entrada

Lee los siguientes datos desde la Entrada Estándar:

• En la $1$-ª línea está escrito un entero $N$. $N$ representa la longitud de la secuencia $A$.
• En la $i$-ésima línea ($1 \le i \le N$) de las siguientes $N$ líneas está escrito un entero $A_i$. Esto representa el $i$-ésimo entero de la secuencia $A$.

Salida

Imprime en la Salida Estándar, en $1$ línea, un entero que represente el número mínimo de intercambios mediante el ordenamiento de burbuja en la secuencia $A'$.

Criterios de calificación

• Para el $10\%$ de la puntuación total, se cumple $N \le 1000$, y para cualesquiera $i, j$ ($1 \le i < j \le N$) se cumple $A_i \ne A_j$.
• Para el $30\%$ de la puntuación total, se cumple $N \le 5000$, y para cualesquiera $i, j$ ($1 \le i < j \le N$) se cumple $A_i \ne A_j$.
• Para el $80\%$ de la puntuación total, para cualesquiera $i, j$ ($1 \le i < j \le N$) se cumple $A_i \ne A_j$.

Ejemplo

Entrada de ejemplo 1

5
10
3
6
8
1

Salida de ejemplo 1

0

Si decidimos intercambiar el primer $10$ y el último $1$ de la secuencia $A$, la secuencia $A'$ queda ordenada, y el número de intercambios del ordenamiento de burbuja es $0$.

Entrada de ejemplo 2

5
3
1
7
9
5

Salida de ejemplo 2

2

Al intercambiar el $3$-er elemento $7$ y el último elemento $5$ de la secuencia $A$, la secuencia $A'$ pasa a ser $3, 1, 5, 9, 7$. El número de intercambios mediante el ordenamiento de burbuja en $A'$ es $2$.

Entrada de ejemplo 3

3
1
2
3

Salida de ejemplo 3

1

Incluso si la secuencia $A$ ya está ordenada desde el principio, es obligatorio realizar un intercambio al crear la secuencia $A'$.