Dãy hoán vị

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

Cho dãy hoán vị ~p~ độ dài ~n~. Với dãy hoán vị ~q~ độ dài ~n~ bất kỳ, gọi ~f(p,q)~ là số cặp chỉ số ~(i,j)~ ~(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~ độ dài ~n~, hãy tìm giá trị nhỏ nhất của ~f(p,q)~.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên của dãy hoán vị ~p~ ~(1 \le p_i \le n)~.
• Dữ liệu đảm bảo dãy ~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)~.

Examples

5
1 2 3 4 5

1

Notes

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