B. Роботын ажил

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

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

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

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

Робот Док шугамын дагуу байрлуулсан $n$ компьютертэй танхимд байгаа ба компьютерүүдийг зүүнээс нь баруун тийш $1$-c $n$ хүртэл дугаарласан. Компьютер бүр Докын эцэст нь авахыг хүсэж буй мэдээллийн яг нэг хэсгийг агуулж байгаа. Компьютерүүд хамгаалалтын системээр тоноглогдсон ба тэдгээрийн $i$ дэхийнх нь учрыг нь олох буюу эвдэхийн тулд бусад компьютерүүдээс мэдээллийн ядаж $a_{i}$ хэсгийг цуглуулсан байх шаардлагатай. Док компьютерийг зөвхөн түүний баруун талд нь байж байж л халдаж чадна.

Робот орчин үеийн технологуудаар угсрагдсан ба цуваа компьютерүүдийн дагуу боломжит хоёр чиглэлээр хоёулангаар нь явж чадах боловч чиглэлээ өөрчлөхөд Докоос их хэмжээний нөөц шаарддаг. Анх тэр $1$ дугаартай компьютерийн дараагийн байрлалд байсан бол мэдээллийн бүх $n$ хэсгийг цуглуулж чадахын тулд чиглэлээ хамгийн багадаа хэдэн удаа өөрчлөх тоог хэл.

Бүх мэдээллийг цуглуулах роботын үйлдлүүдийн ядаж нэг дараалал оршин байх нь тодорхой. Эхлээд Докд мэдээллийн ямар ч хэсэг байгаагүй.

Оролт

Эхний мөрөнд $n$ ($1 ≤ n ≤ 1000$) тоо байна. Хоёр дахь мөрөнд $n$ ширхэг зайгаар тусгаарлагдсан эерэг бүхэл тоон утга $a_{1}, a_{2}, ..., a_{n}$ ($0 ≤ a_{i} < n$) байна. Роботод мэдээллийн бүх хэсгийг цуглуулах зам оршин байх нь тодорхой.

Гаралт

Робот мэдээллийн бүх $n$ хэсгийг цуглуулахад хийгдэх чиглэлээ өөрчлөх хөдөлгөөнүүдийн хамгийн бага тоог илэрхийлэх нэг ширхэг бүхэл тоон утгыг хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

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

Тэмдэглэл

Эхний жишээн дээр та мэдээллийн бүх хэсгийг эхний компьютерээс эхний хэсгийг тэгээд гурав дахь компьютерээс тэгээд чиглэлээ өөрчлөн хоёр дахь компьютер дээр ирэх ба мэдээллийн 2 хэсэг байгаа учраас сүүлийнхийг цуглуулах хамгийн тохиромжтой аргаар цуглуулж чадна.

Хоёр дахь жишээн дээр хамгийн тохиромжтой аргаар мэдээллийн бүх хэсгийг цуглуулахын тулд Док дөрөвдүгээр компьютеррүү очиж мэдээллийн нэг хэсгийг авна, тэгээд тавдугаар компьютеррүү очиж нэг хэсэг дээрээ нэмж нэгийг авна, тэгээд хоёр дахь компьютеррүү очиж ижил аргаар авна, тэгээд гуравдугаар компьютеррүү очих ба хамгийн сүүлд нь нэгрүү очно. Чиглэл өөрчлөгдөж байгаа газрууд нь таваас хоёрруу, тэгээд хоёроос гуравруу, тэгээд гурваас нэгдүгээр компьютерруу очиход солигдож байна.

Гурав дахь жишээн дээр компьютерүүдээс хэсгүүдийг цуглуулах хамгийн тохиромжтой арга нь дараах байдлаар харагдана: 1->3->4->6->2->5->7.

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