Một dãy \(a_1,a_2,…,a_n\) độ dài \(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≤p<n)\) sao cho tổng giá trị của \(p\) phần tử đầu đúng bằng của \((n-p)\) phần tử cuối:

Cho một dãy \(a_1,a_2,…,a_n\) độ dài \(n\). Bạn có thể biến đổi dãy \(a_1,a_2,…,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≤i≤n)\) và tăng \(a_i\) lên \(1\);
• Chọn một vị trí \(i (1≤i≤n)\) mà \(a_i>1\) và trừ \(a_i\) cho \(1\).

Yêu cầu:

• 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.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên \(n (2≤n≤2×10^5 )\) là độ dài dãy \(a\);
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1,a_2,…,a_n (1≤a_i≤20242024)\).

Kết quả:

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

Ví dụ:

Input 1

5
1 2 3 4 5

Output 1

3

Input 2

2
1 2

Output 2

1

Giải thích:

• Ở 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.

Ràng buộc:

• Subtask 1 (15% số điểm): \(n≤10,a_i≤5\);
• Subtask 2 (15% số điểm): \(n≤1000\);
• Subtask 3 (30% số điểm): Không cần thực hiện quá \(2\) thao tác để dãy \(a\) thành dãy đẹp;
• Subtask 4 (40% số điểm): Không có ràng buộc gì thêm.