题目描述

薯条哥有一个长度为$n$的数组$a$,他现在想要选择其中一个数字进行"二进制翻转",他想知道有多少种方式使得反转后的数组总和比不操作的更大

二进制反转:指将$x$的二进制翻转 reverse，反转后去掉前导 0

$12=(1100)_2\;\;\;\;f(12)=(0011)_2 =3$

输入描述

第一行输入一个正整数$n(1 \le n \le 2 \times 10^5)$, 表示数组$a$的长度。

第二行输入$n$个正整数$a_1, a_2,...,a_n(1 \le a_i \le 10^9)$, 表示数组$a$的元素。

输出描述

输出一个整数，表示不同的方式数量。

样例

输入

4
1 3 4 6

输出

0