C. Сувд агуулсан мөр

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

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

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

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

Нэг мөрөнд $n$ ширхэг сувд байна. Эдгээрийг зүүнээс баруун тийш $1$-с $n$ хүртэл дугаарлацгаая. $i$ дугаартай сувд нь $a_{i}$ төрлийнх.

Дараалласан сувднуудын дарааллыг сегмент гэж нэрлэе. Хэрвээ энэ сегмент нь ижил төрлийн хоёр сувд агуулж байвал гоё сегмент гэж нэрлэе.

Сувдтай мөрийг гоё сегментийн тоо хамгийн их байхаар хуваая. Сувд бүр хуваалтын нэг сегментэд л байна.

Оролт гаралт нь маш их хэмжээтэй байж болох тул оролт гаралтын хурдан функцүүдийг ашиглана уу. Жишээ нь: C++ хэлэнд $cin/cout$-ийн оронд $scanf/printf$-ийг ашиглах, $Java$ хэлэнд $Scanner/System.out$-ийн оронд $BufferedReader/PrintWriter$-ийг ашиглана уу.

Оролт

Эхний мөрөнд бүхэл тоон утга $n$ ($1 ≤ n ≤ 3*10^{5}$) байх ба мөрөнд байрлах сувдны тоо.

Хоёр дахь мөрөнд $n$ ширхэг бүхэл тоон утга $a_{i}$ ($1 ≤ a_{i} ≤ 10^{9}$) байх ба $i$-р сувдны төрөл.

Гаралт

Эхний мөрөнд мөрийг хуваахад үүссэн сегментүүдийн тоо болох бүхэл тоон утга $k$-г хэвлэ.

Дараагийн $k$ мөр бүрт хоёр бүхэл тоон утга $l_{j}, r_{j}$ ($1 ≤ l_{j} ≤ r_{j} ≤ n$) байх ба $j$-р сегментийн сувдуудын хамгийн зүүн болон хамгийн баруун талын сувдны дугаар байна.

Та мөрийн зөв хуваалтыг хэвлэх ёстой ба сувд бүр зөвхөн нэг л сегментэд байх ба бүх сегментүүд ижил төрлийн хоёр сувд агуулах ёстой.

Хэрвээ хамгийн тохиромжтой хэд хэдэн шийдэл байвал алийг нь ч хэвлэж болно. Та сегментүүдийг дурын дарааллаар хэвлэж болно.

Мөрийг хуваах ямар ч зөв хуваалт байхгүй бол "$-1$"-г хэвлэ.

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

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

Оролт
5
1 2 3 4 1
Гаралт
1
1 5
Оролт
5
1 2 3 4 5
Гаралт
-1
Оролт
7
1 2 1 3 1 2 1
Гаралт
2
1 3
4 7
Сэтгэгдлүүдийг ачааллаж байна...