A. Жүүс ууцгаая!

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

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

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

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

Берландийн иргэд, ялангуяа оюутнууд эрүүл мэнддээ их анхаардаг гэдгийг хүн бүхэн мэднэ. Берландын оюутнууд их тэвчээртэй ба тэдний уудаг зүйл нь жүржийн шүүс.

Өчигдөр Вася болон түүний найзууд шорлог хийж идсэн ба тэд зөвхөн энэ эрүүл мэндэд тустай ундаагаа л уусан. Тэд нэг торх жүүсээ дуусгасаныхаа дараа нэг хялбархан тоглоом тоглохоор шийдсэн. Шорлог идэхээр ирсэн бүх $n$ хүн тойрч сууна (хүн бүр 0-с $n - 1$ хүртэл давтагдахгүй $b_{i}$ дугаартай болно). 0 дугаартай хүн тоглоомыг эхлүүлсэн (энэ удаад Вася байж таарсан). Тоглоомын ээлжүүдийг 1-с эхлэн бүхэл тоогоор дугаарлана. Хэрвээ $i$-р ээлж нь $b_{i}$ дугаартай хүн дээр таарсан бол дараах байдлаар тоглоно:

  1. Тэр $(b_{i} + 1) mod n$ дугаартай хүнийг тохойгоороо нудрах юм уу, эрүүгээрээ дохих замаар заана ($x$ mod $y$ гэдэг нь $x$-г $y$-т хуваагаад гарсан үлдэгдэл байна).
  2. Хэрвээ $j ≥ 4$ байвал $j - 1$, $j - 2$, $j - 3$ ээлжийн дугаартай байсан тоглогчид өөрсдийн үе дээрээ энэ үеийн $b_{i}$ тоглогчийн хийсэн үйлдлүүдийг хийсэн бол тоглогч маань нэг аяга жүүс ууна;
  3. Ээлж $(b_{i} + 1)$ хүнрүү шилжинэ.

Сүүлийн ээлж дээр заагдсан хүн юу ч хийхгүй.

Асуудал нь Вася маш их жүүс уусан ба тоглоомын зорилгыг ч санаж чадахгүй байна. Гэсэн ч Васяд бүх оролцогчдын (өөрийг нь оролцуулаад) үйлдлүүдийн дараалал байна. Одоо Вася хэрвээ хамгийн тохиромжтой байдлаар тоглосон бол ууж чадах жүүсний хамгийн их хэмжээг олохыг хүсч байна (бусад тоглогчдын үйлдлүүд өөрчлөгдөхгүй). Түүнд туслана уу.

Ямар ч нөхцөлд хүн бүрт уух хангалттай хэмжээний жүүс бий гэж тооцоорой.

Оролт

Эхний мөрөнд бүхэл тоо $n$ ($4 ≤ n ≤ 2000$) байх буюу тоглоомд оролцогчдын тоо байна.

Хоёр дахь мөрөнд тоглоомыг дүрслэнэ: хэрвээ $i$-р ээлжинд тоглосон хүн дараагийн хүнээ тохойгоороо нударсан бол мөрийн $i$-р тэмдэгт нь '$a$' байна, харин эрүүгээрээ дохьсон бол тэмдэгт маань '$b$' байна. Тоглоомийн үргэлжлэх ээлжийн тоо нь хамгийн багадаа 1 хамгийн ихдээ $2000$ байна.

Гаралт

Хэрвээ Вася хамгийн тохиромжтойгоор тоглосон бол ууж чадах жүүсний хамгийн их хэмжээг илэрхийлэх бүхэл тоог хэвлэ.

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

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

Оролт
4
abbba
Гаралт
1
Оролт
4
abbab
Гаралт
0

Тэмдэглэл

Хоёр жишээн дээр хоёулан дээр нь Васяд 1 болон 5 гэсэн хоёр ээлж байна.

Эхний жишээн дээр хэрвээ Вася дараагийн хүнээ эрүүгээрээ заах юм бол тавдугаар ээлжинд нэг шил жүүс уух боломжтой. Энэ тохиолдолд үйлдлүүдийн дараалал "abbbb" хэлбэртэй болно.

Хоёр дахь жишээн дээр 3 болон 4 дахь ээлжинд хийгдсэн үйлдлүүд ялгаатай байгаагаас болж Вася ямар ч жүүс уух боломжгүй.

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