Énoncé du problème

Le tri à bulles est l'un des algorithmes permettant de trier une suite. Supposons que nous voulions trier une suite $A$ de longueur $N$ par ordre croissant. Le tri à bulles échange les positions de $2$ nombres adjacents dès que leur ordre relatif est inversé. Un passage consiste à parcourir la suite du début à la fin et à échanger ces $2$ nombres chaque fois que $A_i > A_{i+1}$ pour $i = 1, 2, \dots, N - 1$ dans cet ordre. Il est connu qu'en répétant ce passage $N - 1$ fois, on trie la suite par ordre croissant.

Le nombre d'échanges effectués par le tri à bulles sur une suite $A$ est le nombre de fois où des entiers sont échangés lorsque l'algorithme ci-dessus est appliqué à la suite $A$. (Bien que les algorithmes et implémentations connus sous le nom de tri à bulles puissent présenter de légères différences dans l'ordre des boucles, leurs bornes et les conditions d'arrêt, il est connu que le nombre d'échanges d'entiers lorsqu'on les applique à la même suite ne change pas en fonction de ces différences.)

Par exemple, le programme suivant est une fonction écrite en langage C qui trie un tableau d'entiers a de longueur n à l'aide du tri à bulles.

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

Tâche

On vous donne une suite $A$ de longueur $N$. Supposons que l'on construise une suite $A'$ en échangeant exactement $1$ fois $2$ entiers situés à des positions arbitraires dans la suite $A$. Écrivez un programme permettant de trouver la valeur minimale du nombre d'échanges effectués par le tri à bulles sur la suite $A'$. (Notez que les $2$ entiers échangés initialement ne sont pas nécessairement adjacents.)

Contraintes

• $1 \le N \le 100000$ : la longueur de la suite $A$.
• $1 \le A_i \le 1000000000$ : la valeur des nombres contenus dans la suite $A$.

Entrée

Lisez les données suivantes depuis l'entrée standard :

• Sur la $1$-re ligne est écrit un entier $N$. $N$ représente la longueur de la suite $A$.
• Sur la $i$-ième ligne ($1 \le i \le N$) des $N$ lignes suivantes est écrit un entier $A_i$. Cela représente le $i$-ième entier de la suite $A$.

Sortie

Affichez sur la sortie standard, en $1$ ligne, un entier représentant le nombre minimal d'échanges effectués par le tri à bulles sur la suite $A'$.

Critères d'évaluation

• Pour $10\%$ des points, $N \le 1000$, et $A_i \ne A_j$ est vérifié pour tous $i, j$ ($1 \le i < j \le N$).
• Pour $30\%$ des points, $N \le 5000$, et $A_i \ne A_j$ est vérifié pour tous $i, j$ ($1 \le i < j \le N$).
• Pour $80\%$ des points, $A_i \ne A_j$ est vérifié pour tous $i, j$ ($1 \le i < j \le N$).

Exemple

Exemple d'entrée 1

5
10
3
6
8
1

Exemple de sortie 1

0

Si l'on échange le premier élément $10$ et le dernier élément $1$ de la suite $A$, la suite $A'$ devient une suite triée, et le nombre d'échanges du tri à bulles est $0$.

Exemple d'entrée 2

5
3
1
7
9
5

Exemple de sortie 2

2

En échangeant le $3$-e élément $7$ et le dernier élément $5$ de la suite $A$, la suite $A'$ devient $3, 1, 5, 9, 7$. Le nombre d'échanges effectués par le tri à bulles sur $A'$ est $2$.

Exemple d'entrée 3

3
1
2
3

Exemple de sortie 3

1

Même si la suite $A$ est déjà triée dès le départ, un échange doit obligatoirement être effectué lors de la création de la suite $A'$.