Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Järjestys

Järjestys


View task | Model solution | Statistics


Järjestys

Time limit:1.00 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 listan alkuun.

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
Esimerkki

Syöte:
5
4 3 1 5 2


Tuloste:
3

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