Тут могл б бути Ваша реклама Наша реклама

Гра Боулінг має наступні правила: на прямій стоїт ряд з k кегель. Відстань між двома сусідніми дорівнює 1. Гравці ходять по черзі. За один хід гравець може збити одну кеглю, або дві, відстань між якими дорівнює 1. Промахуватися не можна. Виграє той, хто зіб'є останню кеглю.

У нашому випадку уск трохи складніше. Вован та Петян - два бізнесмени і вони арендували цілий кегельбан. Тому у їхньому розпорядженні є аж n незалених доріжок боулінга. Під час свого ходу гравець вибирає, на якій доріжці він зробить хід, після чого він здійснює цей хід. Потім другий гравець може вибрати іншу доріжку. І так далі. Умова перемоги, як і раніше, збити останню кеглю.

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

Вхідні дані

Перший рядок містить кількість доріжок n (n ≤ 1000). Другий рядок містить n натуральних чисел ki (ki ≤ 1000) - кількість кегель на доріжці номер i.

Вихідні дані

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