Problembeskrivelse

Boblesortering er en av algoritmene for å sortere en følge. Anta at vi ønsker å sortere en følge $A$ med lengde $N$ i stigende rekkefølge. Boblesortering bytter plass på $2$ nabotall dersom størrelsesforholdet mellom dem er feil. Én gjennomgang består i å gå gjennom følgen fra start til slutt og bytte plass på disse $2$ tallene hver gang $A_i > A_{i+1}$ for $i = 1, 2, \dots, N - 1$ i denne rekkefølgen. Det er kjent at ved å gjenta denne gjennomgangen $N - 1$ ganger vil følgen bli sortert i stigende rekkefølge.

Antallet bytter ved boblesortering på en følge $A$ er antallet ganger heltall bytter plass når algoritmen ovenfor brukes på følgen $A$. (Selv om algoritmer og implementasjoner kjent som boblesortering kan ha små forskjeller i løkkerekkefølge, intervaller og stoppbetingelser, er det kjent at antallet heltallsbytter når de brukes på samme følge ikke endres som følge av disse forskjellene.)

For eksempel er følgende program en funksjon skrevet i C som sorterer en heltallstabell a med lengde n ved hjelp av boblesortering.

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

Oppgave

Det gis en følge $A$ med lengde $N$. Anta at vi lager en følge $A'$ ved å bytte plass på $2$ heltall på vilkårlige posisjoner i følgen $A$ nøyaktig $1$ gang. Skriv et program for å finne den minste mulige verdien for antallet bytter ved boblesortering på følgen $A'$. (Merk at de $2$ heltallene som byttes først ikke nødvendigvis trenger å stå ved siden av hverandre.)

Begrensninger

• $1 \le N \le 100000$: lengden på følgen $A$.
• $1 \le A_i \le 1000000000$: størrelsen på tallene i følgen $A$.

Inndata

Les inn følgende data fra standard inndata:

• På den $1$. linjen står et heltall $N$. $N$ representerer lengden på følgen $A$.
• På den $i$. linjen ($1 \le i \le N$) av de påfølgende $N$ linjene står et heltall $A_i$. Dette representerer det $i$. heltallet i følgen $A$.

Utdata

Skriv ut et heltall på $1$ linje til standard utdata som representerer det minste antallet bytter ved boblesortering på følgen $A'$.

Vurderingskriterier

• For $10\%$ av poengene gjelder $N \le 1000$, og for alle $i, j$ ($1 \le i < j \le N$) gjelder $A_i \ne A_j$.
• For $30\%$ av poengene gjelder $N \le 5000$, og for alle $i, j$ ($1 \le i < j \le N$) gjelder $A_i \ne A_j$.
• For $80\%$ av poengene gjelder for alle $i, j$ ($1 \le i < j \le N$) at $A_i \ne A_j$.

Eksempel

Eksempelinndata 1

5
10
3
6
8
1

Eksempelutdata 1

0

Hvis vi bytter det første tallet $10$ og det siste tallet $1$ i følgen $A$, blir følgen $A'$ ferdig sortert, og antallet bytter i boblesortering blir $0$.

Eksempelinndata 2

5
3
1
7
9
5

Eksempelutdata 2

2

Ved å bytte det $3$. tallet $7$ og det siste tallet $5$ i følgen $A$, blir følgen $A'$ lik $3, 1, 5, 9, 7$. Antallet bytter ved boblesortering på $A'$ er $2$.

Eksempelinndata 3

3
1
2
3

Eksempelutdata 3

1

Selv om følgen $A$ er sortert helt fra starten av, må det utføres et bytte når følgen $A'$ lages.