---
# System prepended metadata

title: Večerja

---

# Večerja

Kralj Bubble XLII. je izbrano družbo povabil na večerjo.  Zamislil si je, da bo na eni strani mize sedelo njegovo veličanstvo, na drugi pa se bodo po vrsti od najmanjšega do največjega razporedili gostje.  Žal nevedni gostje niso počakali, da jim kraljev služabnik dodeli stol, ampak so se usedli, kakor so se pač usedli.  Ko kralj ta nered opazi, ukaže služabniku, naj jih razporedi v pravilnem vrstnem redu, a tako, da bo to za goste čim manj moteče.  "Med seboj lahko menjuješ le sosede.  Pa pohiti, ker smo že vsi lačni!"

Kolikšno je najmanjše število zamenjav, ki jih mora služabnik izvesti, da bo goste uredil od najmanjšega do največjega (ali pa od največjega do najmanjšega --- dobrohotni kralj bo tudi s tem zadovoljen, le da čimprej dobi svojo večerjo ...).

## Vhod

Prva vrstica vsebuje število gostov ($n$), druga pa $n$ števil z intervala $[1, 10^9]$, ki predstavljajo njihove višine.

## Izhod

Izpiši iskano število zamenjav.

## Primer

### Vhod

```
5
180 175 190 170 175
```

### Izhod

```
3
```

### Komentar

V tem primeru lahko najprej med seboj zamenjamo četrtega in petega gosta ...

180, 175, 190, 175, 170

... nato drugega in tretjega ...

180, 190, 175, 175, 170

... nazadnje pa še prvega in drugega ...

190, 180, 175, 175, 170

... in večerja je na mizi!

## Podnaloge

1. podnaloga (20 točk): $n \in [1, 10]$.
2. podnaloga (30 točk): $n \in [1, 1000]$.
3. podnaloga (50 točk): $n \in [1, 10^5]$.
