Một dãy ~a_1, a_2, \dots, a_n~ được gọi là cân bằng nếu có thể chia dãy thành hai đoạn liên tiếp có tổng bằng nhau, tức là tồn tại một vị trí ~p~ (~1 \leq p < n~) sao cho tổng giá trị của ~p~ phần tử đầu dùng bằng của ~(n - p)~ phần tử cuối: $$\sum_{i=1}^{p} a_i = \sum_{i=p+1}^{n} a_i$$

Cho một dãy ~a_1, a_2, \dots, a_n~ độ dài ~n~. Bạn có thể biến dổi dãy ~a_1, a_2, \dots, a_n~ bằng cách thực hiện thao tác sau số lần tùy ý. Mỗi lần thực hiện thao tác có thể tùy ý lựa chọn một trong hai hành động:

• Chọn một vị trí ~i~ (~1 \leq i \leq n~) và tăng ~a_i~ lên 1.

• Chọn một vị trí ~i~ (~1 \leq i \leq n~) mà ~a_i > 1~ và giảm ~a_i~ cho 1.

Hãy thực hiện thao tác trên ít lần nhất để làm cho dãy a cân bằng.

Input

Vào từ tệp BALANCE.INP gồm:

Dòng đầu tiên chứa số nguyên ~n~ (~2 \leq n \leq 2 \times 10^5~) là độ dài dãy ~a~.

Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~1 \leq a_i \leq 20242024~).

Output

Ghi kết quả lên tệp BALANCE.OUT gồm:

Một số nguyên duy nhất là số lần ít nhất cần thực hiện thao tác.

Scoring

Sample Input 1

5
1 2 3 4 5

Sample Output 1

3

Sample Input 2

2
1 2

Sample Output 2

1

Notes

Ở ví dụ 1, ta thực hiện cộng ~a_2~ cho 1, trừ ~a_4~ và ~a_5~ cho 1. Sau 3 lần thực hiện thao tác, dãy ~a~ trở thành ~1, 3, 3, 3, 4~, và có vị trí ~p = 3~ thỏa mãn yêu cầu đề bài.