Cho một dãy số dương \(a_1, a_2, ..., a_n\) ta có thể tách dãy thành nhiều đoạn các số liên tiếp với nhau \(a_i, a_{i+1}, ... ,a_j\), đoạn ít nhất có đúng 1 phần tử đoạn nhiều nhất là tất cả các phần tử. Bạn phân dãy ban đầu thành các đoạn sao cho một phần tử bất kỳ phải tham gia vào một đoạn nào đó, các đoạn phải rời nhau, tổng mỗi đoạn phải bằng nhau biết rằng số phần tử mỗi đoạn không nhất thiết phải bằng nhau.

Input

Dòng đầu tiên chứa một số nguyên \(N (1≤ N ≤ 10000)\) là số phần tử của dãy. Dòng tiếp theo là các phần tử của dãy số cách nhau bởi 1 dấu cách. \((0<a_i<20000)\).

Output

In ra tổng bằng nhau nhỏ nhất của các đoạn có tổng bằng nhau

Example 1

INPUT

6

3 3 2 4 4 8

OUTPUT

8

Giải thích: Chúng ta chia 3 nhóm có tổng bằng 8 là (3 3 2) (4 4) (8).

Example 2

INPUT

6

1 2 3 4 5 6

OUTPUT

21

Giải thích: Chúng ta chia 1 nhóm là tất cả các phần tử có tổng là 21.