Dãy hoán vị

Time limit: 1.0s , Memory limit: 256M , Points: 1000 (partial)

Lưu ý: Bài toán này không chia Subtask.

Cho dãy hoán vị $p$ ~p~ độ dài $n$ ~n~. Với dãy hoán vị $q$ ~q~ độ dài $n$ ~n~ bất kỳ, gọi $f(p,q)$ ~f(p,q)~ là số cặp chỉ số $(i,j)$ ~(i,j)~ $(1 \le i \le j \le n)$ ~(1 \le i \le j \le n)~ thỏa mãn:

$p_i+p_{i+1}+...+p_j=q_i+q_{i+1}+...+q_j$

Yêu cầu: Trong tất cả các dãy hoán vị $q$ ~q~ độ dài $n$ ~n~, hãy tìm giá trị nhỏ nhất của $f(p,q)$ ~f(p,q)~.

Input

Dòng đầu tiên chứa số nguyên $n$ ~n~ $(1 \le n \le 10^5)$ ~(1 \le n \le 10^5)~.
Dòng thứ hai chứa $n$ ~n~ số nguyên của dãy hoán vị $p$ ~p~ $(1 \le p_i \le n)$ ~(1 \le p_i \le n)~.
Dữ liệu đảm bảo dãy $p$ ~p~ là một dãy hoán vị hợp lệ.

Output

In ra giá trị nhỏ nhất của $f(p,q)$ ~f(p,q)~.

Examples

Sample Input

5
1 2 3 4 5

Sample Output

Notes

Trong ví dụ, với dãy hoán vị $q=[3, 5, 4, 2, 1]$ ~q=[3, 5, 4, 2, 1]~, chỉ có cặp chỉ số $(i,j)=(1,5)$ ~(i,j)=(1,5)~ thỏa mãn $p_1+p_2+...+p_5=q_1+q_2+...+q_5$ ~p_1+p_2+...+p_5=q_1+q_2+...+q_5~. Vì vậy, $f(p,q)$ ~f(p,q)~ đạt giá trị nhỏ nhất bằng $1$ ~1~.