Aufgabenstellung

Bubblesort ist einer der Algorithmen zum Sortieren einer Folge. Nehmen wir an, wir möchten eine Folge $A$ der Länge $N$ aufsteigend sortieren. Bubblesort vertauscht die Positionen von $2$ benachbarten Zahlen, wenn deren Größenverhältnis falsch herum ist. Ein Durchlauf besteht darin, die Folge von vorne nach hinten zu durchlaufen und für $i = 1, 2, \dots, N - 1$ in dieser Reihenfolge jeweils die $2$ Zahlen zu vertauschen, falls $A_i > A_{i+1}$ gilt. Es ist bekannt, dass die Folge aufsteigend sortiert wird, wenn man diesen Durchlauf $N - 1$ Mal wiederholt.

Die Anzahl der Vertauschungen durch Bubblesort auf einer Folge $A$ ist die Anzahl der Male, die ganze Zahlen vertauscht werden, wenn der obige Algorithmus auf die Folge $A$ angewendet wird. (Obwohl Algorithmen und Implementierungen, die als Bubblesort bekannt sind, geringfügige Unterschiede in der Schleifenreihenfolge, den Bereichen und den Abbruchbedingungen aufweisen können, ist bekannt, dass sich die Anzahl der Vertauschungen ganzer Zahlen bei Anwendung auf dieselbe Folge durch diese Unterschiede nicht ändert.)

Beispielsweise ist das folgende Programm eine in C geschriebene Funktion, die ein ganzzahliges Array a der Länge n mithilfe von Bubblesort sortiert.

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

Aufgabe

Gegeben ist eine Folge $A$ der Länge $N$. Nehmen wir an, wir erzeugen eine Folge $A'$, indem wir $2$ ganze Zahlen an beliebigen Positionen in der Folge $A$ genau $1$-mal vertauschen. Schreibe ein Programm, das das Minimum der Anzahl der Vertauschungen durch Bubblesort auf der Folge $A'$ bestimmt. (Beachte, dass die $2$ zu Beginn vertauschten ganzen Zahlen nicht unbedingt benachbart sein müssen.)

Einschränkungen

• $1 \le N \le 100000$: die Länge der Folge $A$.
• $1 \le A_i \le 1000000000$: die Größe der in der Folge $A$ enthaltenen Zahlen.

Eingabe

Lies die folgenden Daten von der Standardeingabe ein:

• In der $1$. Zeile steht eine ganze Zahl $N$. $N$ gibt die Länge der Folge $A$ an.
• In der $i$-ten Zeile ($1 \le i \le N$) der folgenden $N$ Zeilen steht eine ganze Zahl $A_i$. Diese gibt die $i$-te ganze Zahl der Folge $A$ an.

Ausgabe

Gib auf der Standardausgabe in $1$ Zeile eine ganze Zahl aus, die die minimale Anzahl der Vertauschungen durch Bubblesort auf der Folge $A'$ angibt.

Bewertungskriterien

• Für $10\%$ der Gesamtpunktzahl gilt $N \le 1000$, und für alle $i, j$ ($1 \le i < j \le N$) gilt $A_i \ne A_j$.
• Für $30\%$ der Gesamtpunktzahl gilt $N \le 5000$, und für alle $i, j$ ($1 \le i < j \le N$) gilt $A_i \ne A_j$.
• Für $80\%$ der Gesamtpunktzahl gilt für alle $i, j$ ($1 \le i < j \le N$) $A_i \ne A_j$.

Beispiel

Beispiel-Eingabe 1

5
10
3
6
8
1

Beispiel-Ausgabe 1

0

Wenn wir die erste Zahl $10$ und die letzte Zahl $1$ der Folge $A$ vertauschen, wird die Folge $A'$ zu einer sortierten Folge, und die Anzahl der Vertauschungen bei Bubblesort beträgt $0$.

Beispiel-Eingabe 2

5
3
1
7
9
5

Beispiel-Ausgabe 2

2

Indem man die $3$. Zahl $7$ und die letzte Zahl $5$ der Folge $A$ vertauscht, wird die Folge $A'$ zu $3, 1, 5, 9, 7$. Die Anzahl der Vertauschungen durch Bubblesort auf $A'$ beträgt $2$.

Beispiel-Eingabe 3

3
1
2
3

Beispiel-Ausgabe 3

1

Selbst wenn die Folge $A$ von Anfang an sortiert ist, muss beim Erzeugen der Folge $A'$ eine Vertauschung durchgeführt werden.