Testo del problema

Il bubble sort è uno degli algoritmi per ordinare una sequenza. Supponiamo di voler ordinare una sequenza $A$ di lunghezza $N$ in ordine crescente. Il bubble sort scambia le posizioni di $2$ numeri adiacenti ogni volta che il loro ordine relativo è invertito. Una singola passata consiste nello scorrere la sequenza dall'inizio alla fine e nello scambiare quei $2$ numeri ogni volta che $A_i > A_{i+1}$ per $i = 1, 2, \dots, N - 1$ in quest'ordine. È noto che ripetendo questa passata $N - 1$ volte la sequenza viene ordinata in modo crescente.

Il numero di scambi effettuati dal bubble sort su una sequenza $A$ è il numero di volte in cui vengono scambiati degli interi quando l'algoritmo descritto sopra viene applicato alla sequenza $A$. (Sebbene gli algoritmi e le implementazioni noti come bubble sort possano presentare lievi differenze nell'ordine dei cicli, negli intervalli e nelle condizioni di terminazione, è noto che il numero di scambi di interi applicato alla stessa sequenza non varia a causa di tali differenze.)

Ad esempio, il seguente programma è una funzione scritta in linguaggio C che ordina un array di interi a di lunghezza n utilizzando il 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;
      }
    }
  }
}

Compito

Data una sequenza $A$ di lunghezza $N$, supponiamo di creare una sequenza $A'$ scambiando esattamente $1$ volta $2$ interi in posizioni arbitrarie nella sequenza $A$. Scrivi un programma per trovare il minimo numero possibile di scambi effettuati dal bubble sort sulla sequenza $A'$. (Nota che i $2$ interi scambiati inizialmente non devono necessariamente essere adiacenti.)

Vincoli

• $1 \le N \le 100000$: la lunghezza della sequenza $A$.
• $1 \le A_i \le 1000000000$: la grandezza dei numeri contenuti nella sequenza $A$.

Input

Leggi i seguenti dati dallo Standard Input:

• Sulla $1$ª riga è scritto un intero $N$. $N$ rappresenta la lunghezza della sequenza $A$.
• Sulla $i$-esima riga ($1 \le i \le N$) delle successive $N$ righe è scritto un intero $A_i$. Questo rappresenta l'$i$-esimo intero della sequenza $A$.

Output

Stampa sullo Standard Output, in $1$ riga, un intero che rappresenta il numero minimo di scambi effettuati dal bubble sort sulla sequenza $A'$.

Criteri di valutazione

• Per il $10\%$ del punteggio totale, vale $N \le 1000$, e per ogni $i, j$ ($1 \le i < j \le N$) vale $A_i \ne A_j$.
• Per il $30\%$ del punteggio totale, vale $N \le 5000$, e per ogni $i, j$ ($1 \le i < j \le N$) vale $A_i \ne A_j$.
• Per l'$80\%$ del punteggio totale, per ogni $i, j$ ($1 \le i < j \le N$) vale $A_i \ne A_j$.

Esempio

Input di esempio 1

5
10
3
6
8
1

Output di esempio 1

0

Se scambiamo il primo $10$ e l'ultimo $1$ della sequenza $A$, la sequenza $A'$ diventa una sequenza ordinata, e il numero di scambi nel bubble sort è $0$.

Input di esempio 2

5
3
1
7
9
5

Output di esempio 2

2

Scambiando il $3$° elemento $7$ e l'ultimo elemento $5$ della sequenza $A$, la sequenza $A'$ diventa $3, 1, 5, 9, 7$. Il numero di scambi effettuati dal bubble sort su $A'$ è $2$.

Input di esempio 3

3
1
2
3

Output di esempio 3

1

Anche se la sequenza $A$ è già ordinata fin dall'inizio, è comunque obbligatorio effettuare uno scambio quando si crea la sequenza $A'$.