Маленький Крис знает, что играть в домино неинтересно, он думает, что в игре слишком много случайного и совсем не требуется умение. Поэтому он решил поиграть с доминошками и устроить «домино шоу».

Крис расположил n доминошек в ряд, поставив каждую вертикально вверх. В начале он выбирает некоторые доминошки, и толкает каждую из них либо влево, либо вправо. Однако, между каждыми двумя доминошками, толкаемыми в одном направлении, обязательно находится хотя бы одна доминошка, которую Крис толкнул в противоположном направлении.

Через каждую секунду каждая доминошка, падающая влево, толкает соседнюю доминошку слева. Аналогично, доминошки, падающие вправо, толкают соседние доминошки справа. Когда на вертикальную доминошку падают соседние доминошки с обеих сторон, она не двигается из-за баланса сил слева и справа. Рисунок ниже показывает один из возможных примеров описанного процесса.

Вам даны изначальные направления, в которых Крис толкает доминошки. Найдите количество доминошек, которые останутся стоять вертикально в конце процесса!