АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Шинэ жилийн эмх замбараагүй байдал

Өнөөдөр шинэ жилийн баярын өдөр бөгөөд хүмүүс Wonderland roll rolloster аялалд гарахаар  болоод байна.

n тооны хүмүүс дараалалд орсон байгаа бөгөөд тэднийг эхнээс нь 1-ээс эхлээд n хүртэл дугаарласан байгаа.

Дараалалд байгаа аливаа хүн өөрийнхөө урд байгаа хүний урд гарахыг хүсвэл хахууль өгөөд байраа сольж болдог ба

нэг хүн зөвхөн хоёр хүнд л хахууль өгч чадна.

Жишээ нь n=8 үед 5 дугаартай хүн 4 дугаартай хүнд хахууль өгөхөд [1,2,3,5,4,6,7,8] дараалал ингэж хувирдаг.

Мөн тухайн хүнд анх өгсөн дугаар дахиж солигддоггүй. Танд гаднаас n урттай хахууль авсан байгаа хүмүүсийн дараалал өгөгдөх юм.

Та хэдэн хүн хахууль авсан байгааг уг дарааллаас олох ёстой.

Оролт:

t     ( 1≤ t ≤ 10) тестийн тоо

n    (1 ≤ n ≤ 10⁵ ) дараалын урт

A[1],A[2] …… A[n]

Гаралт:

Авсан хахуулийн тоо. Хэрвээ уг дараалал хэтэрхий замбараагүй бөгөөд өгсөн нөхцлийг зөрчсөн тохиолдолд “ Too chaotic ” гэж хэвлэ.

Жишээ:

Оролт:

2

5

2 1 5 3 4

5

2 5 1 3 4

Гаралт:

3

Too chaotic

Тайлбар:

1-р жишээ:  [ 2,1,5,3,4  ] -> [1,2,5,3,4]  -> [1,2,3,5,4] -> [1,2,3,4,5]

2 дугаартай хүн ( 1 ) дугаартай хүнд хахууль өгсөн байна.

5 дугаартай хүн ( 3,4 ) дугаартай хүмүүст хахууль өгсөн байна.

2-р жишээ: 5 дугаартай хүн ( 1,3,4 ) дугаартай хүмүүст хахууль өгсөн замбараагүй буюу 5 дугаартай хүн нь 3 хүнд хахууль өгсөн байна.

Орчуулсан  : Дархан-Уул аймгийн Союз сургуулийн 12-р ангийн сурагч Б.Сумьяабазар