Lýsing á verkefni

Bóluröðun (Bubble sort) er eitt af reikniritunum til að raða runu. Gerum ráð fyrir að við viljum raða runu $A$ af lengd $N$ í hækkandi röð. Bóluröðun víxlar sætum á $2$ aðliggjandi tölum ef stærðarröð þeirra er öfug. Ein yfirferð felst í því að skanna rununa frá upphafi til enda og víxla þessum $2$ tölum í hvert sinn sem $A_i > A_{i+1}$ fyrir $i = 1, 2, \dots, N - 1$ í þessari röð. Það er þekkt að með því að endurtaka þessa yfirferð $N - 1$ sinnum raðast runan í hækkandi röð.

Fjöldi víxlana með bóluröðun á runu $A$ er fjöldi skipta sem heiltölum er víxlað þegar reikniritinu hér að ofan er beitt á rununa $A$. (Þótt reiknirit og útfærslur sem nefnast bóluröðun geti haft smávægilegan mun á röð lykkja,abilum og stöðvunarskilyrðum, þá er vitað að fjöldi víxlana á heiltölum þegar þeim er beitt á sömu rununa breytist ekki vegna þessa munar.)

Til dæmis er eftirfarandi forrit fall skrifað í C sem raðar heiltölufylki a af lengd n með bóluröðun.

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

Verkefni

Gefin er runa $A$ af lengd $N$. Gerum ráð fyrir að við búum til runu $A'$ með því að víxla $2$ heiltölum á handahófskenndum stöðum í rununni $A$ nákvæmlega $1$ sinni. Skrifið forrit til að finna minnsta mögulega fjölda víxlana með bóluröðun á rununni $A'$. (Athugið að heiltölurnar $2$ sem víxlað er í upphafi þurfa ekki endilega að vera aðliggjandi.)

Takmarkanir

• $1 \le N \le 100000$: lengd rununnar $A$.
• $1 \le A_i \le 1000000000$: stærð talnanna í rununni $A$.

Inntak

Lesið eftirfarandi gögn úr staðalinntaki:

• Á $1$. línu er skrifuð heiltala $N$. $N$ táknar lengd rununnar $A$.
• Á $i$-tu línu ($1 \le i \le N$) af næstu $N$ línum er skrifuð heiltala $A_i$. Hún táknar $i$-tu heiltöluna í rununni $A$.

Úttak

Prentið á staðalúttak í $1$ línu heiltölu sem táknar minnsta mögulega fjölda víxlana með bóluröðun á rununni $A'$.

Stigagjöf

• Fyrir $10\%$ af heildarstigum gildir $N \le 1000$, og fyrir öll $i, j$ ($1 \le i < j \le N$) gildir $A_i \ne A_j$.
• Fyrir $30\%$ af heildarstigum gildir $N \le 5000$, og fyrir öll $i, j$ ($1 \le i < j \le N$) gildir $A_i \ne A_j$.
• Fyrir $80\%$ af heildarstigum gildir fyrir öll $i, j$ ($1 \le i < j \le N$) að $A_i \ne A_j$.

Dæmi

Dæmi um inntak 1

5
10
3
6
8
1

Dæmi um úttak 1

0

Ef við víxlum fyrstu tölunni $10$ og síðustu tölunni $1$ í rununni $A$, þá verður runan $A'$ röðuð runa og fjöldi víxlana í bóluröðun verður $0$.

Dæmi um inntak 2

5
3
1
7
9
5

Dæmi um úttak 2

2

Með því að víxla $3$. tölunni $7$ og síðustu tölunni $5$ í rununni $A$ verður runan $A'$ jöfn $3, 1, 5, 9, 7$. Fjöldi víxlana með bóluröðun á $A'$ er $2$.

Dæmi um inntak 3

3
1
2
3

Dæmi um úttak 3

1

Jafnvel þótt runan $A$ sé þegar röðuð frá upphafi verður samt að framkvæma víxlun þegar runan $A'$ er búin til.