Treść zadania

Sortowanie bąbelkowe to jeden z algorytmów sortowania ciągów. Załóżmy, że chcemy posortować ciąg $A$ o długości $N$ w porządku rosnącym. Sortowanie bąbelkowe zamienia miejscami $2$ sąsiednie liczby, jeśli relacja mniejszości między nimi jest zaburzona. Jedno przejście polega na przeglądaniu ciągu od początku do końca i zamienianiu tych $2$ liczb zawsze, gdy $A_i > A_{i+1}$ dla $i = 1, 2, \dots, N - 1$ w tej kolejności. Wiadomo, że powtórzenie takiego przejścia $N - 1$ razy sortuje ciąg w porządku rosnącym.

Liczba zamian w sortowaniu bąbelkowym ciągu $A$ to liczba zamian liczb całkowitych wykonywanych podczas zastosowania powyższego algorytmu do ciągu $A$. (Chociaż algorytmy i implementacje znane jako sortowanie bąbelkowe mogą wykazywać drobne różnice w kolejności pętli, zakresach czy warunkach zakończenia, wiadomo, że liczba zamian liczb całkowitych po zastosowaniu do tego samego ciągu nie zmienia się w zależności od tych różnic.)

Na przykład poniższy program to napisana w języku C funkcja sortująca tablicę liczb całkowitych a o długości n za pomocą sortowania bąbelkowego.

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

Zadanie

Dany jest ciąg $A$ o długości $N$. Załóżmy, że tworzymy ciąg $A'$, zamieniając dokładnie $1$ raz $2$ liczby całkowite na dowolnych pozycjach w ciągu $A$. Napisz program, który wyznaczy minimalną możliwą liczbę zamian w sortowaniu bąbelkowym ciągu $A'$. (Zauważ, że $2$ liczby całkowite zamieniane na początku nie muszą ze sobą sąsiadować.)

Ograniczenia

• $1 \le N \le 100000$: długość ciągu $A$.
• $1 \le A_i \le 1000000000$: wielkość liczb występujących w ciągu $A$.

Wejście

Wczytaj następujące dane ze standardowego wejścia:

• W $1$-szym wierszu zapisana jest liczba całkowita $N$. $N$ oznacza długość ciągu $A$.
• W $i$-tym wierszu ($1 \le i \le N$) spośród kolejnych $N$ wierszy zapisana jest liczba całkowita $A_i$. Oznacza ona $i$-tą liczbę całkowitą ciągu $A$.

Wyjście

Wypisz na standardowe wyjście w $1$ wierszu liczbę całkowitą oznaczającą minimalną liczbę zamian w sortowaniu bąbelkowym ciągu $A'$.

Kryteria oceniania

• Dla danych wartych $10\%$ łącznej liczby punktów spełniony jest warunek $N \le 1000$ oraz dla dowolnych $i, j$ ($1 \le i < j \le N$) zachodzi $A_i \ne A_j$.
• Dla danych wartych $30\%$ łącznej liczby punktów spełniony jest warunek $N \le 5000$ oraz dla dowolnych $i, j$ ($1 \le i < j \le N$) zachodzi $A_i \ne A_j$.
• Dla danych wartych $80\%$ łącznej liczby punktów dla dowolnych $i, j$ ($1 \le i < j \le N$) zachodzi $A_i \ne A_j$.

Przykład

Wejście przykładowe 1

5
10
3
6
8
1

Wyjście przykładowe 1

0

Jeśli zamienimy pierwsze $10$ i ostatnie $1$ w ciągu $A$, ciąg $A'$ stanie się ciągiem posortowanym, a liczba zamian w sortowaniu bąbelkowym wyniesie $0$.

Wejście przykładowe 2

5
3
1
7
9
5

Wyjście przykładowe 2

2

Zamieniając $3$-cią liczbę $7$ oraz ostatnią liczbę $5$ w ciągu $A$, otrzymujemy ciąg $A'$ równy $3, 1, 5, 9, 7$. Liczba zamian w sortowaniu bąbelkowym ciągu $A'$ wynosi $2$.

Wejście przykładowe 3

3
1
2
3

Wyjście przykładowe 3

1

Nawet jeśli ciąg $A$ jest od samego początku posortowany, podczas tworzenia ciągu $A'$ należy obowiązkowo wykonać zamianę.