Задача E. Весы на весах ≡

Условие

Чашечные весы расположили друг на друге так, как указано на рисунке, и на чаши верхних весов положили по одной гирьке. Сколько весов окажутся в состоянии равновесия?

Формат входных данных

Первая строка входного файла содержит одно натуральное число n - число гирек. В следующей строке через пробел расположены n натуральных чисел x_i - вес i-й гирьки в порядке просмотра слева направо. Гарантируется, что n - степень числа 2.

Формат выходных данных

Выведите одно неотрицательное целое число - количество весов, которые будут находиться в равновесии.

Ограничения

2 ≤ n ≤ 2¹⁶

1 ≤ x_i ≤ 9

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

В примере 15 весов и 16 гирек. В состоянии равновесия окажутся 6 весов (выделены на рисунке зеленым цветом) - на каждой из них вес на левой чаше равен весу на правой чаше.

Примеры тестов

16
1 4 2 3 4 3 2 1 2 2 3 3 5 1 3 1

6