Một dãy \(a_{1},a_{2},\ldots,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 \leq 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:

\[\sum_{i = 1}^{p}a_{i} = \sum_{i = p + 1}^{n}a_{i}\]

Cho một dãy \(a_{1},a_{2},\ldots,a_{n}\) độ dài \(n\). Bạn có thể biến đổi dãy \(a_{1},a_{2},\ldots,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à trừ \(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.

Dữ liệu vào:

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

• Dòng thứ hai chứa \(n\) số nguyên dương \(a_{1},a_{2},\ldots,a_{n}\) \(\left( 1 \leq a_{i} \leq 20242024 \right)\).

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ụ:

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 \leq 10,\ a_{i} \leq 5\)

• Subtask \(2\) (\(15\%\) số điểm): \(n \leq 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.