Колись, у царстві, жила принцеса із порожньою послідовністю та колекцією магічних куль. Кожна куля мала свій розмір, де розмір $i$-тої кулі ($1 \leq i \leq N$) дорівнював $2 \times A_i$.

Ця принцеса любила виконувати чарівні операції з цими кулями. Вона вирішила виконати послідовність з $N$ операцій. Під час кожної операції вона додавала кулю до кінця послідовності та виконувала такі кроки:

1. Якщо послідовність мала одну або менше куль, операція завершувалася.
2. Якщо остання куля та передостання куля у послідовності мали різні розміри, операція завершувалася.
3. Якщо остання куля та передостання куля у послідовності мали однаковий розмір, принцеса видаляла ці дві кулі та додавала нову кулю до кінця послідовності. Ця нова куля мала розмір, рівний сумі розмірів двох видалених куль. Після цього вона поверталася до кроку 1 та повторювала процес.

Принцеса хотіла знати, скільки куль залишиться в послідовності після виконання $N$ операцій.

Input Specification

У першому рядку введіть ціле число $n$ - кількість куль в колекції. $(1 \leq n \leq 2 \times 10^5)$

У другому рядку введіть $n$ цілих чисел, розділених пробілом, що відповідають розмірам куль $a_1$ $a_2$ $\ldots$ $a_n$. $(0 \leq a_i \leq 10^9)$

Output Specification

Вивести кількість куль у послідовності після $N$ операцій.

Sample Input 1

7
2 1 1 3 5 3 3

Sample Output 1

3

Sample Input 2

5
0 0 0 1 2

Sample Output 2

4