Problem Statement

The virtual YouTuber Uzuki Rou loved coffee beans. She loved them so much that she even roasted the beans herself. Each coffee bean in this world has a "deliciousness" represented by a positive integer, which indicates how delicious the bean is.

Uzuki Rou has a total of $N$ coffee beans, represented by a sequence $a$. The deliciousness of the $i$-th coffee bean from the left is $a_i$.

Since coffee beans in the sequence $a$ with varying deliciousness would contain a lot of bitterness, Uzuki Rou has decided to freely perform an operation any number of times so that all coffee beans have equal deliciousness.

The operation that can be performed is as follows.

• Let $K$ be the current number of elements in the sequence $a$. Roast the $i(1{\leq}i{\leq}K-1)$-th coffee bean from the left and the $i+1$-th coffee bean, which are $2$ adjacent coffee beans, into $1$ bean. The deliciousness of the newly created coffee bean is $a_i+a_{i+1}$. Note that this can only be performed when $K>1$ (since adjacent coffee beans are required).

By repeating the above operation, Uzuki Rou wants to make the deliciousness of all coffee beans equal while maximizing the number $R$ of coffee beans remaining at the end of the operations. Find the maximum number $R$ of coffee beans remaining at the end of the operations.

Input

$N$
$a_1 \ a_2 \ ...\ a_N$

• All inputs are integers
• $1{\leq}N{\leq}10^5$
• $1{\leq}a_i{\leq}10^2$

Output

Print a newline at the end.

Sample

8
5 2 2 3 1 1 4 3

3

1
50

1

60
36 45 67 64 100 2 3 22 52 64 9 22 53 63 45 60 56 26 68 33 87 23 91 81 71 34 37 91 51 26 44 76 93 1 34 100 3 22 53 23 61 8 85 90 49 6 40 45 66 80 36 32 21 88 40 42 78 97 99 6 

3