Järjestys II

• Time limit: 1.00 s
• Memory limit: 128 MB

Annettuna on taulukko, jossa on $n$ lukua. Tavoitteesi on järjestää taulukon luvut pienimmästä suurimpaan.

Voit joka siirrolla valita minkä tahansa taulukon luvun ja siirtää sen johonkin toiseen paikkaan. Montako siirtoa tarvitset vähintään taulukon järjestämiseksi?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $n$: taulukon koko.

Seuraavalla rivillä on $n$ kokonaislukua $x_1,x_2,\ldots,x_n$: taulukon sisältö.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: pienin siirtojen määrä.

Rajat

• $1 \le n \le 10^5$
  
• $1 \le x_i \le 10^9$
  

Esimerkki

Syöte:
5
2 6 4 7 4

Tuloste:
2