C. Төмөр замын вагонуудыг байрлуулах

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Хязгааргүй урт төмөр зам дээр $n$ ширхэг вагоноос тогтох нэгэн галт тэрэг байв.Тус галт тэрэгний вагонууд нь $1$-ээс $n$ хүртэл дугаарлагдсан(бүх вагоны дугаар ялгаатай байна) байх ба дурын дарааллаар байрласан байх юм.

Дэвид Блэйн эдгээр вагонуудыг дугаарынх нь дагуу өсөх дарааллаар байрлуулахыг хүсжээ.Тэрээр нэг үйлдлээр ямар нэгэн вагоныг байрнаас нь алга болгох ба уг вагоныг өөрийнхөө хүслээр галт тэрэгний эхэнд эсвэл төгсгөлд шилжүүлж тавих юм.Тэгвэл Дэвид Блэйн галт тэргийг өсөх дараалалд оруулж байрлуулахын тулд шаардагдах хамгийн бага үйлдлийн тоог олно уу.

Оролт

Эхний мөрөнд галт тэрэгний вагоны тоо болох бүхэл тоо $n$ ($1 ≤ n ≤ 100 000$) өгөгдөнө.

2-дахь мөрөнд галт тэрэгний вагонуудын дугаарууд болох $n$ ширхэг бүхэл тоо $p_{i}$ ($1 ≤ p_{i} ≤ n$, $p_{i} ≠ p_{j}$ if $i ≠ j$)-уудын цуваа өгөгдөнө.

Гаралт

Галт тэрэгний вагонуудыг дугаарынх нь дагуу өсөх дараалалд оруулж байрлуулахын тулд шаардагдах хамгийн бага үйлдлийн тоог хэвлэнэ.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
5
4 1 2 5 3
Гаралт
2
Оролт
4
4 1 3 2
Гаралт
2

Тэмдэглэл

Эхний жишээнд та эхлээд $4$-дэх вагоныг дараа нь $5$-дахь вагоныг галт тэрэгний төгсгөлд шилжүүлж тавина.

Сэтгэгдлүүдийг ачааллаж байна...