Problem G
Stökiga listor
Languages
en
sv
Doris har precis lärt sig att programmera och deltar i sin första programmeringstävling. Hon har stött på ett problem som kan lösas genom att sortera ett antal häftiga heltal. För att sortera de tänker hon använda den inbyggda sorteringsfunktionen i det revolutionerande nya programmeringsspråket Meowscript. Språket är dock inte helt färdigt än och dess sorteringsfunktion verkar vara lite buggig.
Hjälp Doris avgöra hur många element som står vid fel index i den stökiga listan av heltal, jämfört med ifall den skulle ha varit sorterad i stigande ordning.
Indata
Första raden innehåller ett heltal $N$ ($1\leq N \leq 10^6$), antalet heltal som finns i listan. Andra raden innehåller de $N$ heltal $0\leq A_ i \leq 10^9$ som befinner sig i den stökiga listan.
Utdata
Skriv ut ett heltal - antal element i listan som befinner sig på fel position jämfört med en sorterad lista.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poängvärde |
Gränser |
|
$1$ |
$20$ |
$N \leq 2$ |
|
$2$ |
$20$ |
Den inbyggda sorteringsfunktionen sorterar i minskande ordning |
|
$3$ |
$20$ |
$N \leq 1000$ |
|
$4$ |
$40$ |
Inga ytterligare begränsningar |
| Sample Input 1 | Sample Output 1 |
|---|---|
5 1 1 2 3 5 |
0 |
| Sample Input 2 | Sample Output 2 |
|---|---|
7 3 1 4 1 5 9 2 |
6 |
