Cho dãy gồm ~n~ số nguyên không âm ~a_1, a_2, \dots, a_n~.

Một đoạn liên tiếp ~a_l, a_{l+1}, \dots, a_r~ được gọi là đoạn đại diện nếu trung bình cộng của các phần tử trong đoạn bằng trung bình cộng của toàn bộ dãy, tức là

~\frac{a_l+a_{l+1}+\dots+a_r}{r-l+1}=\frac{a_1+a_2+\dots+a_n}{n}~.

Hãy xác định độ dài nhỏ nhất của một đoạn đại diện.

Đoạn gồm toàn bộ dãy luôn là một đoạn đại diện, vì vậy đáp án luôn tồn tại.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(1 \le n \le 2 \cdot 10^5)~;

• Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1, a_2, \dots, a_n~ ~(0 \le a_i \le 10^6)~.

Output

In ra một số nguyên duy nhất là độ dài nhỏ nhất của một đoạn đại diện.

Scoring

Sample Input 1

4
1 4 2 5

Sample Output 1

2

Sample Input 2

5
2 5 1 4 3

Sample Output 2

1

Sample Input 3

2
1 2

Sample Output 3

2

Notes

Trung bình cộng của toàn bộ dãy trong ví dụ thứ nhất bằng ~3~. Đoạn gồm hai phần tử ~4,2~ cũng có trung bình cộng bằng ~3~. Không có đoạn gồm một phần tử nào thỏa mãn.

Trong ví dụ thứ hai, phần tử cuối cùng có giá trị bằng trung bình cộng của toàn bộ dãy.

Trong ví dụ thứ ba, không có đoạn gồm một phần tử nào có trung bình cộng bằng ~\frac{3}{2}~, vì vậy đoạn đại diện ngắn nhất là toàn bộ dãy.