A. Медиан тэгшилгээ

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

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

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

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

Сурагч Вася програмчлал болон математикийн ном унших дуртай. Тэр саяхан медиан тэгшилгээ (эсвэл медиан шүүр) аргыг болон үүний шинжлэх ухаан болон инженерчлэлийн салбар дахь хэрэглээг тодорхойлсон шинжлэх ухааны өгүүллийг уншсан. Васяд энэ аргын санаа нь маш их таалагдсан ба үүнийгээ практик дээр туршихаар шийдсэн.

Медиан тэгшилгээ аргын хамгийн хялбар хувилбарыг $a_{1}, a_{2}, ..., a_{n}$ тоонуудын дараалал дээр хэрэгжүүлээд дараах алгоритмаар шинэ $b_{1}, b_{2}, ..., b_{n}$ тоонуудын дараалал гаргаж авна:

  • $b_{1} = a_{1}$, $b_{n} = a_{n}$ буюу шинэ дарааллын эхний болон сүүлийн тоонууд анхны дарааллын харгалзах тоонуудтай тэнцүү байна.
  • $i = 2, ..., n - 1$ хувьд $b_{i}$ утга нь $a_{i - 1}$, $a_{i}$ ба $a_{i + 1}$ гурван утгын медиан нь байна.

Бүрдэл гурван тооны медиан гэдэг нь гурван тоог өсөх дарааллаар байрлуулаад хоёр дахь байранд байгаа утгыг хэлнэ. Жишээлбэл 5, 1, 2 бүрдлийн хувьд медиан нь 2 бол 1, 0, 1 бүрдлийн хувьд медиан нь 1 байна.

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

Нэг удаа хэрэгжүүлж үзээд Вася гарч буй дараалалруу хараад хэрвээ би алгоритмыг дахин нэг удаа хэрэгжүүлээд гарсан үр дүн дээр нь дахин хэрэгжүүлээд үргэлжлүүлбэл яах вэ? гэж бодсон. Вася хэд хэдэн жишээн дээр хэрэгжүүлсний дараа медиан тэгшилгээ аргыг хэд хэдэн удаа хэрэглэсний дараа дараалал өөрчлөгдхөө больж байгааг олсон. Хэрвээ бид дараалалд медиан тэгшилгээ аргыг хэрэгжүүлэхэд дараалал өөрчлөгдөхгүй бол уг дарааллыг тогтвортой гэж хэлнэ.

Одоо харин Вася дараалал үргэлж төгсгөлд нь тогтвортой болж байгаа болов уу гэж бодож байна. Тэр таныг өгөгдсөн тэг нэгийн дараалал байнга тогтвортой болж байгаа үгүйг тодорхойлдог програм бичихийг хүсч байна. Түүнчлэн хэрвээ дараалал тогтвортой болж байвал дараа нь та дараалал ямар болж байгааг мөн тогтвортой болгохын тулд анхны дараалал дээр медиан тэгшилгээний алгоритмыг хэдэн удаа хэрэгжүүлэхийг тодорхойлох ёстой.

Оролт

Оролтын эхний мөрөнд бүхэл тоон утга $n$ ($3 ≤ n ≤ 500 000$) байх буюу анхны дарааллын урт юм.

Дараагийн мөрөнд $n$ бүхэл тоон утга $a_{1}, a_{2}, ..., a_{n}$ ($a_{i} = 0$ эсвэл $a_{i} = 1$) байх буюу анхны дарааллыг өгнө.

Гаралт

Хэрвээ дараалал хэзээ ч тогтвортой болохгүй бол $ - 1$-г хэвлэ.

Бусад тохиолдолд эхлээд анхны дарааллыг тогтвортой болгоход хэрэгжүүлэгдэх медиан тэгшилгээ алгоритмын боломжит хамгийн бага тоог хэвлэ. Хоёр дахь мөрөнд зайгаар тусгаарлагдсан $n$ бүхэл тоо буюу тогтвортой болсон дарааллыг хэвлэнэ.

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

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

Оролт
4
0 0 1 1
Гаралт
0
0 0 1 1
Оролт
5
0 1 0 1 0
Гаралт
2
0 0 0 0 0

Тэмдэглэл

Хоёр дахь жишээн дээр тогтворжилт нь хоёр үйлдэлд явагдана: , мөн $00000$ дараалал нь мэдээж тогтвортой байна.

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