Tehtävänanto

Kuplalajittelu on yksi lukujonon lajittelualgoritmeista. Oletetaan, että haluamme lajitella pituutta $N$ olevan lukujonon $A$ nousevaan järjestykseen. Kuplalajittelu vaihtaa $2$ vierekkäisen luvun paikkaa, jos niiden suuruusjärjestys on väärä. Yksi läpikäynti koostuu siitä, että lukujono käydään läpi alusta loppuun ja kyseiset $2$ lukua vaihdetaan keskenään aina, kun $A_i > A_{i+1}$, arvoilla $i = 1, 2, \dots, N - 1$ tässä järjestyksessä. Tiedetään, että toistamalla tämä läpikäynti $N - 1$ kertaa lukujono saadaan lajiteltua nousevaan järjestykseen.

Lukujonon $A$ kuplalajittelun vaihtojen lukumäärä tarkoittaa sitä, kuinka monta kertaa kokonaislukujen paikkoja vaihdetaan, kun yllä olevaa algoritmia sovelletaan lukujonoon $A$. (Vaikka kuplalajitteluna tunnetuissa algoritmeissa ja toteutuksissa voi olla pieniä eroja silmukoiden järjestyksessä, rajoissa ja lopetusehdoissa, tiedetään, että kokonaislukujen vaihtojen lukumäärä samaan lukujonoon sovellettuna ei muutu näiden erojen vuoksi.)

Esimerkiksi seuraava ohjelma on C-kielellä kirjoitettu funktio, joka lajittelee pituutta n olevan kokonaislukutaulukon a kuplalajittelulla.

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

Tehtävä

Annetaan pituutta $N$ oleva lukujono $A$. Oletetaan, että muodostetaan lukujono $A'$ vaihtamalla $2$ mielivaltaisissa kohdissa olevan kokonaisluvun paikkaa lukujonossa $A$ täsmälleen $1$ kerran. Kirjoita ohjelma, joka etsii lukujonon $A'$ kuplalajittelun vaihtojen lukumäärän pienimmän mahdollisen arvon. (Huomaa, että aluksi vaihdettavien $2$ kokonaisluvun ei tarvitse välttämättä olla vierekkäisiä.)

Rajoitukset

• $1 \le N \le 100000$: lukujonon $A$ pituus.
• $1 \le A_i \le 1000000000$: lukujonoon $A$ sisältyvien lukujen suuruus.

Syöte

Lue vakiosyötteestä seuraavat tiedot:

• $1$. rivillä on kokonaisluku $N$. $N$ ilmaisee lukujonon $A$ pituuden.
• Seuraavien $N$ rivin $i$. rivillä ($1 \le i \le N$) on kokonaisluku $A_i$. Tämä ilmaisee lukujonon $A$ $i$. kokonaisluvun.

Tuloste

Tulosta vakiotulosteeseen $1$ riville kokonaisluku, joka ilmaisee lukujonon $A'$ kuplalajittelun vaihtojen pienimmän mahdollisen lukumäärän.

Arvosteluperusteet

• Arvosteludatasta $10\%$ pisteistä täyttää ehdon $N \le 1000$, ja kaikilla $i, j$ ($1 \le i < j \le N$) pätee $A_i \ne A_j$.
• Arvosteludatasta $30\%$ pisteistä täyttää ehdon $N \le 5000$, ja kaikilla $i, j$ ($1 \le i < j \le N$) pätee $A_i \ne A_j$.
• Arvosteludatasta $80\%$ pisteistä kaikilla $i, j$ ($1 \le i < j \le N$) pätee $A_i \ne A_j$.

Esimerkki

Esimerkkisyöte 1

5
10
3
6
8
1

Esimerkkituloste 1

0

Jos lukujonon $A$ ensimmäinen luku $10$ ja viimeinen luku $1$ vaihdetaan keskenään, lukujonosta $A'$ tulee valmiiksi lajiteltu jono, jolloin kuplalajittelun vaihtojen lukumäärä on $0$.

Esimerkkisyöte 2

5
3
1
7
9
5

Esimerkkituloste 2

2

Vaihtamalla lukujonon $A$ $3$. luku $7$ ja viimeinen luku $5$ keskenään saadaan lukujono $A'$, joka on $3, 1, 5, 9, 7$. Lukujonon $A'$ kuplalajittelun vaihtojen lukumäärä on $2$.

Esimerkkisyöte 3

3
1
2
3

Esimerkkituloste 3

1

Vaikka lukujono $A$ olisi valmiiksi lajiteltu jo alussa, lukujonoa $A'$ muodostettaessa on silti suoritettava vaihto.