Маленький Крис знает, что играть в домино неинтересно, он думает, что в игре слишком много случайного и совсем не требуется умение. Поэтому он решил поиграть с доминошками и устроить «домино шоу».
Крис расположил n доминошек в ряд, поставив каждую вертикально вверх. В начале он выбирает некоторые доминошки, и толкает каждую из них либо влево, либо вправо. Однако, между каждыми двумя доминошками, толкаемыми в одном направлении, обязательно находится хотя бы одна доминошка, которую Крис толкнул в противоположном направлении.
Через каждую секунду каждая доминошка, падающая влево, толкает соседнюю доминошку слева. Аналогично, доминошки, падающие вправо, толкают соседние доминошки справа. Когда на вертикальную доминошку падают соседние доминошки с обеих сторон, она не двигается из-за баланса сил слева и справа. Рисунок ниже показывает один из возможных примеров описанного процесса.
Вам даны изначальные направления, в которых Крис толкает доминошки. Найдите количество доминошек, которые останутся стоять вертикально в конце процесса!
Примечание
Первый пример показан на рисунке. Четыре доминошки, оставшиеся стоять вертикально, выделены оранжевым цветом.
Во втором тестовом примере все доминошки падают, так как первая доминошка падает на все остальные.
В последнем примере, единственную доминошку не толкали ни в одном направлении.