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

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

$12=(1100)_2 , f(12) = (0011)_2 = 3$

输入:

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

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

输出:

输出次数

样例

输入:

4
1 3 4 6

输出:

0