Hide

Problem B
Bogletics Intermission

/problems/hi.bogleticsintermission/file/statement/is/img-0001.png
Mynd fengin af commons.wikimedia.org
Meðan beðið er eftir flatbökunni frá Trominos ætla þeir sem mættir eru í partíið hjá KFFÍ að horfa á einhverja þætti. Ekki voru margar tillögur svo það endar með því að Atli komi með uppástungu sem enginn nennir að mótmæla, svo það endar með því að allir horfi á Bogletics. Á einhverjum tímapunkti í þættinum lendir aðalkarakterinn í smá vandræðum. Hann er með $n$ hluti og $n + 1$ staði til að geyma þá. Þar sem hann getur ekki haldið á svo mörgu í einu og er þegar með ýmislegt á sér getur hann aðeins haldið á einum hlut í einu. Eins og stendur eru hlutirnir dreifðir einhvern veginn á fyrstu $n$ staðina, en þeir eru ekki í þeirri röð sem hann vill hafa þá. Ef það eina sem hann getur gert er að taka einn hlut og færa hann yfir á tóman stað, hvað þarf hann að framkvæma margar færslur til að allt sé á réttum stað?

Inntak

Fyrsta lína inntaksins inniheldur eina tölu $n$ sem uppfyllir $1 \leq n \leq 10^5$, fjöldi hluta sem þarf að raða. Næst kemur lína með $n$ heiltölum $k_1, k_2, \dots , k_ n$ sem uppfylla $1 \leq k_ i \leq n$. Gildi $k_ i$ segir þá til um númer hvaða stað hluturinn sem er núna á stað $i$ ætti að vera. Ekkert gildanna verður jafnt $n + 1$ þar sem staður $n + 1$ á ávallt að vera aftur tómur í lokin. Gildin verða auk þess öll ólík.

Úttak

Eina línu með einni heiltölu sem segir til um lágmarksfjölda færslna sem þarf til þess að koma öllu á réttan stað.

Sample Input 1 Sample Output 1
4
1 3 2 4
3
Sample Input 2 Sample Output 2
8
7 4 6 8 1 3 5 2
11

Please log in to submit a solution to this problem

Log in