CSES - Leirikisa 2 - Järjestys
  • Time limit: 0.50 s
  • Memory limit: 128 MB

Annettuna on lista, jossa on luvut 1,2,\ldots,n jossakin järjestyksessä, ja tehtäväsi on järjestää listan luvut. Jokaisella siirrolla saat valita yhden luvun ja siirtää sen mihin tahansa paikkaan listassa.

Mikä on pienin määrä siirtoja, joilla saat listan järjestykseen?

Syöte

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

Seuraavalla rivillä on n lukua, jotka kuvaavat listan sisällön.

Tuloste

Tulosta yksi kokonaisluku: pienin siirtojen määrä.

Rajat

  • 1 \le n \le 10^5

Esimerkki

Syöte:

5
3 2 1 5 4

Tuloste:

3

Selitys: vaiheet ovat [3,2,1,5,4] \rightarrow [1,3,2,5,4] \rightarrow [1,2,3,5,4] \rightarrow [1,2,3,4,5].