Given an array of N integers, you can do some operations on it

Given an array of N integers, you can do some operations on it. In each operation, you may choose two adjacent elements a[i] and a[i+1], and do either of the following two –

    1. Replace a[i] with a[i] + a[i+1] and delete a[i+1].

    2. Replace a[i+1] with a[i] + a[i+1] and delete a[i].

Note, performing any of these operations will reduce the array size by 1. Find the max array size, you can obtain, by doing these operations, such that, at last, all the elements of the final array are equal.

Print that maximum final size of the array.

Input Format –

The first line contains a single integer N, denoting the number of values in the array. Then, N lines follow, where each line contains a single integer, denoting the array values.

Output Format –

Print a single line, containing a single integer, the answer to the problem.

note
Constraints
1 <= N <= 2000

1 <= array values <= 1,00,000

view_list
Examples
Input:
4

1

2

2

1

Output:
2

Explanation:
We can finally obtain an array, of size 2, where each of the values of the array would be 3.