Bartek er þekktur teknótónlistarframleiðandi og er um þessar mundir að fullkomna næsta smell sinn. Hann hefur búið til lag sem samanstendur af $n$ töktum (beats), sem eru númeraðir í röð frá $1$ til $n$. Eftir að hafa eytt klukkustundum í tónlistarforriti var hann í þann mund að fara að flytja út mp3-skrána, en tók þá eftir því að taktarnir eru núna í röðinni $a_1, a_2, \dots, a_n$. Bartek þarf að koma töktunum í hækkandi röð, þ.e. $1, 2, \dots, n$.

Forritið leyfir tvær tegundir aðgerða:

• Færa síðasta taktinn í hvaða sæti sem er, t.d. $(2, 4, 1, 5, \underline{3}) \to (2, \underline{3}, 4, 1, 5)$.
• Færa hvaða takt sem er fremst, t.d. $(2, 4, 1, \underline{5}, 3) \to (\underline{5}, 2, 4, 1, 3)$.

Hver er lágmarksfjöldi aðgerða sem þarf til að raða töktunum í hækkandi röð?

Inntak

Fyrsta línan inniheldur heiltölu $n$ ($1 \le n \le 200\,000$), sem táknar fjölda takta.

Önnur línan inniheldur $n$ innbyrðis ólíkar heiltölur $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n; a_i \ne a_j$), sem tákna núverandi röð takta í forritinu.

Úttak

Prentaðu eina heiltölu – lágmarksfjölda aðgerða sem þarf.

Dæmi

Inntak 1

6
3 2 5 4 1 6

Úttak 1

4

Inntak 2

9
3 1 2 5 6 4 9 7 8

Úttak 2

6

Athugasemd

Við byrjum með taktarununa $(3, 2, 5, 4, 1, 6)$. Hér er ein leið til að ná óskaðri röð í fjórum aðgerðum:

• Færa síðasta taktinn um tvö sæti til vinstri: $(3, 2, 5, \underline{6}, 4, 1)$.
• Færa takt $2$ fremst: $(\underline{2}, 3, 5, 6, 4, 1)$.
• Færa takt $1$ fremst: $(\underline{1}, 2, 3, 5, 6, 4)$.
• Færa síðasta taktinn um tvö sæti til vinstri: $(1, 2, 3, \underline{4}, 5, 6)$.

Það er hægt að fá hækkandi röð á annan hátt með fjórum aðgerðum, en það er ekki hægt í þremur aðgerðum, svo niðurstaðan er $4$.