Слонопотам — фигура, состоящая из трёх клеток, образующих «уголок». Эту фигуру можно поворачивать на 90, 180 и 270 градусов, так что получаются 4 возможных положения:
XX XX .X X.
X. .X XX XX
Слонопотамы — мирные фигуры, в отличие от классических шахматных фигур, они не бьют никакие клетки, два слонопотама могут стоять даже рядом друг с другом — главное, чтобы они занимали разные клетки.
У Васи есть доска \(2\times n\) клеток, на которой он хочет разместить несколько слонопотамов. К сожалению, часть клеток доски уже заняты пешками, на эти клетки ставить другие фигуры нельзя. С другой стороны, пешки дружат со слонопотамами, поэтому тоже не бьют слонопотамов, даже если они стоят рядом.
Зная расположение пешек на доске, подскажите Васе, какое наибольшее количество слонопотамов он может одновременно разместить на доске так, чтобы они не пересекались друг с другом и не занимали клетки с пешками.