Здесь могла бы быть Ваша реклама Наша реклама

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

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

Вован ходит первым и ему очень интересно узнать, сколько различных выигрышных ходов у него есть. Два хода считаются различными, если хотя бы одна кегля, сбитая на одном ходе, не является сбитой на другом или наоборот.

Входные данные

Первая строка содержит количество дорожек n (n ≤ 1000). Вторая строка содержит n натуральных чисел ki (ki ≤ 1000) - количество кегель на дорожке номер i.

Выходные данные

Выведите количество выигрышных ходов Вована.