D. Сэлгэмэл

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

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

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

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

$1$-ээс $n$ тооны сэлгэмэл гэдэг нь $1$-ээс $n$ тоонууд бүгд яг нэг, нэг удаа орсон ямар нэгэн дарааллыг хэлнэ. Жишээлбэл (1), (4,3,5,1,2), (3,2,1) гэсэн дарааллууд сэлгэмэл мөн. Харин (1,1), (4,3,1), (2,3,4) эдгээр нь биш. Сэлгэмэлтэй холбоотой маш олон бодлогууд байдаг. Эдгээрээс танаар нэгийг нь бодуулая. Хэн нэгэн хэд хэдэн сэлгэмлийг бичиж байгаад тэдгээрийнхээ тоонуудыг хооронд нь холисон гэж төсөөл. Холисон тоонуудаа танд өгсөн бол тэдгээрийг анхны байсан сэлгэмэл тус бүрээр нь ялгаж харуул.

Оролт

Эхний мөрөнд $N$$(1≤N≤10^5)$ тоо өгөгдөнө. Энэ нь танд нийтдээ хэдэн тоо өгөхийг хэлнэ. Дараагийн мөрөнд $N$ ширхэг тоо зайгаар тусгаарлагдан өгөгдөнө. Тоонууд нь утгаараа $1$-ээс багагүй $10^5$-аас ихгүй байна.

Гаралт

Хэрэв өгөгдсөн тоонууд нь хэд хэдэн сэлгэмэл болж чадаж байвал гаралтын эхний мөрөнд $M$ тоо байх ба энэ нь хэдэн бүлэг сэлгэмэл болж чадахыг илэрхийлнэ. Сэлгэмлүүдийг давхцаагүй л бол ямар ч дугаараар дугаарлаж болно. Дараагийн мөр нь $N$ ширхэг тооноос бүтэх ба эдгээрийн $i$ дэх тооны хувьд оролтын $i$ дэх тоо хэд дугаартай сэлгэмэлд харьяалагдахыг илэрхийлнэ. Олон боломжит шийдтэй бол алийг нь ч гаргасан болно. Харин хэд хэдэн сэлгэмэл болж чадахгүй бол $-1$ гэж гарга.

[Орчуулга хяналт хийгдээгүй. ^_^ ... Codeforces Mongolian Translation Team]

Орчуулсан: Naranbayar

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

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

Тэмдэглэл

In the first sample test the array is split into three permutations: $(2, 1)$, $(3, 2, 1, 4, 5)$, $(1, 2)$. The first permutation is formed by the second and the fourth elements of the array, the second one -- by the third, the fifth, the sixth, the seventh and the ninth elements, the third one -- by the first and the eigth elements. Clearly, there are other splitting variants possible.

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