B. Хүн аалз

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

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

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

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

Петр Паркер Доктор Наймаалжтай нэгэн тоглоом тоглохыг хүсжээ. Уг тоглоом нь циклүүдийн талаарх тоглоом юм. Цикл гэдэг нь оройнуудын дараалал бөгөөд ингэхдээ эхний орой нь 2-дахь оройтой холбогдсон, 2-дахь орой нь 3-дахь оройтой холбогдсон гэх мэтчилэн явсаар сүүлийн орой нь эхний оройтой холбогдсон байх юм. Түүнчлэн цикл нь тусдаа салангид дан оройг агуулсан байж болно.

Анхандаа $k$ ширхэг цикл байх бөгөөд эдгээрийн $i$-дахь цикл нь яг $v_{i}$ ширхэг оройгоос тогтсон байх юм. Тоглогчид ухаалаг тоглох ба өөрөөр хэлбэл зөв үйлдэл хийж тоглох ажээ. Петр тоглоомыг эхлүүлэх бөгөөд ээлж болгон дээр нэг тоглогч нь бүх боломжит циклүүд дундаас дор хаяж 2 ширхэг орой агуулах (жишээлбэл $x$ ширхэг оройтой цикл сонгосон гэж үзье) нэгэн циклийг сонгох ёстой ба уг циклийг $p$ болон $x - p$ ширхэг оройнууд агуулах 2 ширхэг циклээр солих ёстой байв. Энд $1 ≤ p < x$ нь тоглогчийн сонгосон тоо байна. Ямар ч үйлдэл хийж чадахгүй болсон тоглогч тоглоомд ялагдах ба өөрөөр хэлбэл амь насаа алдах юм!

Петр Доктор Наймаалжтай жинхэнээсээ тоглохоосоо өмнө анхны циклүүдийн олонлог дээр ямар нэгэн тоглох арга барил туршиж үзэхийг хүсжээ. Анхандаа түүнд хоосон олонлог байв. $i$-дахь туршилт дээр тэрээр уг олонлогт $a_{i}$ ширхэг орой бүхий нэгэн циклийг нэмнэ (уг олонлог нь мулти-олонлог бөгөөд 2 болон түүнээс олон тооны ижил циклүүдийг агуулсан байж болох юм). Тест бүрийн дараа Петр хэрэв тоглогчид тоглоомыг одоо байгаа циклүүдийн олонлог дээр тогловол хэн уг тоглоомд ялахыг мэдэхийг хүсжээ.

Петр математиктаа үнэхээр сайн хэдий ч энэ удаад тэрээр танаас тусламж хүсжээ.

Оролт

Оролтын эхний мөрөнд ганц бүхэл тоо $n$ ($1 ≤ n ≤ 100 000$) өгөгдөх ба энэ нь Петр-ын хийх туршилтын тоог илэрхийлнэ.

2-дахь мөрөнд $n$ ширхэг зайгаар тусгаарлагдсан бүхэл тоонууд $a_{1}, a_{2}, ..., a_{n}$ ($1 ≤ a_{i} ≤ 10^{9}$)-ууд өгөгдөх ба эдгээрийн $i$-дахь тоо нь $i$-дахь тестийн өмнө циклүүдийн олонлогт нэмэгдэх циклийн оройн тоог илэрхийлнэ.

Гаралт

Тестүүдийн үр дүнг оролтод өгөгдсөн дарааллын дагуу хэвлэнэ үү. Хэрэв тоглоомыг эхлүүлэх тоглогч ялах бол $1$ бусад тохиолдолд $2$ гэж хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
3
1 2 3
Гаралт
2
1
1
Оролт
5
1 1 5 1 1
Гаралт
2
2
2
2
2

Тэмдэглэл

Эхний жишээг авч үзье:

Петр-ын эхний тест дээр уг олонлогт $1$ ширхэг оройтой ганц цикл байх бөгөөд эхний тоглогч ямар нэгэн үйлдэл хийж чадахгүй ба тоглоомд ялагдал хүлээх юм.

2-дахь тест дээр уг олонлогт $1$ ширхэг оройтой 1 цикл болон $2$ ширхэг оройтой 1 цикл байх юм. Аль ч тоглогч нь $1$ ширхэг оройтой цикл дээр үйлдэл хийж чадахгүй ба эхний тоглогч нь 2-дахь циклийг 2 ширхэг $1$ оройтой цикл болгон солих бөгөөд ингэснээр 2-дахь тоглогч үйлдэл хийж чадахгүй болох ба тоглоом ялагдал хүлээнэ.

3-дахь тест дээр ул олонлогт $1$, $2$ болон $3$ ширхэг оройтой циклүүд байх юм. Сүүлийн тест-тэй адилаар аль ч тоглогч нь эхний цикл дээр үйлдэл хийж чадахгүй. Эхний тоглогч 3-дахь циклийг $1$ ширхэг оройтой 1 цикл болон $2$ ширхэг оройтой 1 цикл болгон солино. Одоо олонлог нь $1$, $1$, $2$, $2$ ширхэг оройтой циклүүдтэй болно. 2-дахь тоглогчийн цорын ганц хийж чадах үйлдэл нь $2$ ширхэг оройтой нэг циклийг нь $1$ ширхэг оройтой $2$ цикл болгон солих юм. Ингэснээр олонлог нь $1$, $1$, $1$, $1$, $2$ ширхэг оройтой циклүүдтэй болох ба эхний тоглогч сүүлийн циклийг нь $1$ оройтой $2$ цикл болгон сольсноор тоглоомд ялах юм.

2-дахь жишээг авч үзье:

$1$ оройтой циклүүд олонлогт байна гэдэг нь олонлогт байхгүй байхтай яг ижил юм. Учир нь аль ч тоглогч нь эдгээр циклүүд дээр үйлдэл хийж чадахгүй.

Петр-ын 3-дахь тест дээр $5$ оройтой нэг цикл байх ба (бусад нь хамаагүй) эхний тоглогчид 2 сонголт байх юм: уг циклийг $1$ болон $4$ оройтой циклүүдээр солих эсвэл $2$ болон $3$ оройтой циклүүдээр солих.

  • Хэрэв тэрээр уг циклийг $1$ болон $4$ оройтой циклүүдээр соливол: зөвхөн 2-дахь цикл нь асуудал болох юм. 2-дахь тоглогч 2-дахь циклийг $2$ оройтой 2 цикл болгон солих ба ингэснээр эхний тоглогч үүсэх 2 ширхэг $2$ оройтой циклүүдийн аль нэгийг нь $1$ оройтой циклүүдээр солих цор ганц сонголттой үлдэх юм. Үүний дараа 2-дахь тоглогч үлдсэн $2$ оройтой цикл дээр яг ижил үйлдэл хийх ба ингэснээр эхний тоглогч ямар ч үйлдэл хийж чадахгүй болох бөгөөд тоглоомд ялагдал хүлээнэ.
  • Хэрэв тэрээр уг циклийг $2$ болон $3$ оройтой циклүүдээр соливол: 2-дахь тоглогч $3$ оройтой циклийг $1$ оройтой болон $2$ оройтой 2 ширхэг циклээр солино. Одоо нэгээс олон оройтой циклүүд зөвхөн $2$ оройтой 2 ширхэг цикл болох ба өмнөх жишээнд үзүүлснээр $2$ оройтой $2$ ширхэг циклтэй тоглоомын хувьд 2-дахь тоглогч тоглоомд ялах юм.

Ингэснээр аль ч тохиолдолд эхний тоглогч тоглоомд ялагдал хүлээнэ.

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