Problembeskrivning

Bubbelsortering är en av algoritmerna för att sortera en talföljd. Anta att vi vill sortera en talföljd $A$ av längd $N$ i stigande ordning. Bubbelsortering byter plats på $2$ intilliggande tal om deras storleksordning är omvänd. En genomsökning består i att gå igenom talföljden från början till slut och byta plats på de $2$ talen varje gång $A_i > A_{i+1}$ för $i = 1, 2, \dots, N - 1$ i denna ordning. Det är känt att om man upprepar denna genomsökning $N - 1$ gånger så sorteras talföljden i stigande ordning.

Antalet byten med bubbelsortering på en talföljd $A$ är antalet gånger som heltal byter plats när ovanstående algoritm tillämpas på talföljden $A$. (Även om algoritmer och implementationer som kallas bubbelsortering kan ha mindre skillnader i loopordning, intervall och avslutningsvillkor, är det känt att antalet heltalsbyten när de tillämpas på samma talföljd inte förändras av dessa skillnader.)

Till exempel är följande program en funktion skriven i C som sorterar ett heltalsfält a av längd n med hjälp av bubbelsortering.

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

Uppgift

En talföljd $A$ av längd $N$ är given. Anta att vi skapar en talföljd $A'$ genom att byta plats på $2$ heltal på godtyckliga positioner i talföljden $A$ exakt $1$ gång. Skriv ett program som hittar det minsta möjliga antalet byten med bubbelsortering på talföljden $A'$. (Observera att de $2$ heltal som byter plats först inte nödvändigtvis behöver ligga intill varandra.)

Begränsningar

• $1 \le N \le 100000$: längden på talföljden $A$.
• $1 \le A_i \le 1000000000$: storleken på talen som ingår i talföljden $A$.

Indata

Läs in följande data från standardinmatningen:

• På den $1$:a raden står ett heltal $N$. $N$ anger längden på talföljden $A$.
• På den $i$:te raden ($1 \le i \le N$) av de följande $N$ raderna står ett heltal $A_i$. Detta anger det $i$:te heltalet i talföljden $A$.

Utdata

Skriv ut ett heltal på $1$ rad till standardutmatningen som anger det minsta antalet byten med bubbelsortering på talföljden $A'$.

Bedömningskriterier

• För $10\%$ av poängen gäller $N \le 1000$, och för alla $i, j$ ($1 \le i < j \le N$) gäller $A_i \ne A_j$.
• För $30\%$ av poängen gäller $N \le 5000$, och för alla $i, j$ ($1 \le i < j \le N$) gäller $A_i \ne A_j$.
• För $80\%$ av poängen gäller för alla $i, j$ ($1 \le i < j \le N$) att $A_i \ne A_j$.

Exempel

Exempelindata 1

5
10
3
6
8
1

Exempelutdata 1

0

Om vi byter plats på det första talet $10$ och det sista talet $1$ i talföljden $A$ blir talföljden $A'$ redan sorterad, och antalet byten i bubbelsortering blir $0$.

Exempelindata 2

5
3
1
7
9
5

Exempelutdata 2

2

Genom att byta plats på det $3$:e talet $7$ och det sista talet $5$ i talföljden $A$ blir talföljden $A'$ lika med $3, 1, 5, 9, 7$. Antalet byten med bubbelsortering på $A'$ är $2$.

Exempelindata 3

3
1
2
3

Exempelutdata 3

1

Även om talföljden $A$ är sorterad redan från början måste ett byte utföras när talföljden $A'$ skapas.