16086번 - Дайн 다국어

Хүмүүс харь гаригаас ирсэн аварга том өтнүүдтэй эцсийн тулалдаан хийх гэж байгаа. Яг n тооны өтнүүд болон хүмүүс тулалдах гэж байгаа. 

Тагнуулын мэдээгээр бол i – р хүнийг ганцхан i – р өт л ялж чадна. 

Генерал хүмүүсээ жагсаасан ба i – р хүний эсрэг ai – р өт тулалдах гэж байгааг мэдсэн. Бүх хүмүүс тулаандаа ялсан тохиолдолд л хүмүүс дайнд ялна.

Эхлээд генерал i – р хүнийг жагсаалын i – р байрлалд зогсоосон. Тулаан эхлэх дөхсөн байгаа тул генерал жагсаалынхаа дарааллыг өөрчлөх хэрэгтэй байгаа ба тэрээр зөвхөн жагсаалын сүүлд байгаа хүнийг жагсаалын эхэнд авчирч л чадах ба энэ үйлдлийг нэг удаа хийхэд 1 секунд зарцуулдаг. Уг үйлдлийн дараа бусад хүмүүсийн байрлал бүгд нэгээр нэмэгдэнэ.

Генералд хүмүүсийг дайнд ялуулах байрлалд оруулахын тулд хамгийн багадаа ямар хугацаа хэрэгтэйг тооцоолох програм бич.

Эхний мөрөнд талуудын дайчдын тоо болох  n бүхэл тоо өгөгдөнө (1 ≤ n ≤ 2 ∙ 10⁵). 

Хоёр дахь мөрөнд a₁, a₂, …, a_n гэсэн n ширхэг ялгаатай бүхэл тоо өгөгдөх ба энд ai нь жагсаалын i – рт байрлах хүнтэй тулалдах өтний дугаар юм (1 ≤ a_i ≤ n, хэрэв i ≠ j бол a_i ≠ a_j байна). 

Генерал хүмүүсийг ялуулахын тулд хамгийн багадаа хэдэн секунд зарцуулах ёстойг илэрхийлэх k тоог гаргана. Хэрэв өтнүүдийг ялах боломжгүй бол “-1” тоог гаргана. 

Эхний жишээн дээр дайчид дараах байдлаар тулна:

Өтнүүд    1    6    4    2    3    5
Хүмүүс    1    2    3    4    5    6

1 дугаартай өт тулаанд ялах тул хүмүүс дайнд ялж чадахгүй. Эхний байр солилтын дараа тулаан дараах байдалтай болно:

Өтнүүд    1    6    4    2    3    5
Хүмүүс    6    1    2    3    4    5

Энд 5 – р өт тулаанд ялах тул дахиж байр солилт хийх хэрэгтэй. Хоёр дах байр солилтын дараа дараах байдалтай болно:

Өтнүүд    1    6    4    2    3    5
Хүмүүс    5    6    1    2    3    4

Энд 2, 3, 6 – р өтнүүд ялна. Иймд дахин нэг байр солилт хийх ба үүний үр дүнд хүмүүс дайнд ялах болно.

Өтнүүд    1    6    4    2    3    5
Хүмүүс    4    5    6    1    2    3