Школьник Вася очень любит читать книжки по программированию и математике. Недавно он прочёл в энциклопедии статью, в которой рассказывалось о методе медианного сглаживания и его многочисленных применениях в науке и технике. Идея метода Васе очень понравилась, и он решил опробовать его на практике.

При использовании простейшего варианта медианного сглаживания по последовательности чисел a₁, a₂, ..., a_n строится новая последовательность чисел b₁, b₂, ..., b_n по следующему алгоритму:

• b₁ = a₁, 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.

Чтобы не усложнять себе задачу, Вася решил применять метод только к последовательностям, состоящим из нулей и единиц.

Проделав нехитрую процедуру один раз, Вася посмотрел на получившуюся последовательность и подумал: что будет, если снова применить к ней алгоритм, а потом применить его к следующему результату и так далее? Рассмотрев пару примеров, Вася обнаружил, что через несколько применений медианного сглаживания последовательность может перестать изменяться. Будем говорить, что последовательность стабильна, если она не изменяется при применении к ней медианного сглаживания.

Васе стало интересно, всегда ли последовательность рано или поздно становится стабильной. Он просит вас написать программу, которая по заданной последовательности нулей и единиц определит, становится ли она когда-нибудь стабильной, и если да, то сколько раз для этого нужно применить к ней метод медианного сглаживания.