B. Ширээний теннис

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

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

оролт standard input

гаралт standard output

Петя, Гена хоёр ширээний теннис тоглох их дуртай. Тоглоом дараах дүрмээр явагдана: нэг тоглолт хэд хэдэн үетэй, үе бүрт тоглогчид хэд хэдэн удаа бөмбөгийг тоглолтонд оруулна (цаашид бөмбөг тоглолтонд оруулахыг падааж гэнэ). Падааж бүрт аль нэг тоглогч $1$ оноо авна. Түрүүлж $t$ оноо авсан нь тэр тоглолтонд хожно. Тэгээд дараагийн үе эхлэх ба оноо ахин $0$-ээс эхлэнэ. Түрүүлж $s$ удаа хожсон нь тэр өдрийн ялагч болох юм. Энд $s$ болон $t$ нь эерэг бүхэл тоо байна.

Тоглоомыг сонирхолтой болгохын тулд Петя, Гена хоёр тоглолт бүрийн өмнө $s$ болон $t$ тоонуудыг сонгоно. Түүнээс гадна тэр хоёр дурсгал болгож тоглолт бүрийхээ тэмдэглэлийг хадгална. Өөрөөр хэлбэл падааж бүрт оноо авсан тоглогчийг дарааллуулан тэмдэглэнэ. Тэмдэглэлд тоглогчдын аль нэг нь $t$ оноо авсан үед тэр тоглогч хожно, харин тоглогчдын аль нэг нь түрүүлж $s$ хожил авсан үед тэр өдрийн ялагч болно.

Петя, Гена хоёр хуучныхаа тоглолтын тэмдэглэлийг олж гэнэ. Харамсалтай нь тэмдэглэл дэхь падаажны дараалал тоглолтуудыг зааглаагүй байсан ба $s$, $t$ тоонууд мэдэгдэхгүй байв. Тэгээд тоглогчид $s$ болон $t$-ийн утга хэд байж болохыг боджээ. Та $s$ болон $t$-н авч болох бүх боломжийн тоог олж өгнө үү.

Оролт

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

Хоёрдахь мөрөнд $a_{i}$ $(1 \leq i \leq n)$ гэсэн $n$ ширхэг тоонууд зайгаар тусгаарлагдан байна. Хэрэв $a_{i} = 1$ бол $i$ дэхь падаажинд Петя оноо авсан гэсэн үг, харин $a_{i} = 2$ бол $i$ дэхь падаажинд Гена оноо авсан гэсэн үг.

Тэмдэглэл бүрд таарах зөв $s$, $t$ тоо олдож байх албагүй.

Гаралт

Эхний мөрөнд $s$ болон $t$-ийн авч болох боломжийн тоо $k$-г хэвлэнэ үү.

Дараагийн $k$ мөрөнд, мөр бүрд $s$ болон $t$-ийн хувилбар болох $s_{i}$ болон $t_{i}$-ийг хэвлэ. Боломжуудыг $s_{i}$-ийн өсөх дарааллаар хэвлэх ба $s_{i}$ нь тэнцүү үед $t_{i}$-ийн өсөх дарааллаар хэвлэнэ үү.

Орчуулсан: Бат-Од

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

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