Trong đại hội toán học 2023, mỗi nhóm cử ra 1 thành viên để thực hiện thi cá nhân, ai tính nhanh nhất. Bài toán cho rằng:

Có một số nguyên N có thể viết thành dãy S = (1, 2, …, N). Nhiệm vụ của mỗi thành viên thực hiện duy nhất 1 lần là chọn ra hai phần tử trong dãy và đổi chỗ chúng cho nhau. Sau đó chọn ra vị trí M (1 ≤ M < N) sao cho tổng của M phần tử đầu tiên bằng tổng của N – M phần tử cuối cùng. Tìm số phép hoán đổi vị trí.

Ví dụ: N = 3, S = (1, 2, 3) có 2 phép đổi chỗ đổi (1, 2, 3) và (3, 2, 1).

Yêu cầu: Bạn hãy giúp thành viên của nhóm tìm ra số phép hoán đổi vị trí.

Dữ liệu vào:

Từ tập tin văn bản NUMSWAPS.INP có cấu trúc như sau:

• Dòng đầu tiên là 1 số nguyên N
• Dòng tiếp theo chứa N số nguyên không âm ~a_1, a_2, ... a_N~ (~a_i~ ≤ ~10^9~) cách nhau 1 khoảng trắng.

Dữ liệu ra:

Ghi ra tập tin văn bản NUMSWAPS.OUT gồm N số tìm được cách nhau 1 dấu cách.

Subtasks

Subtask #1 (30 điểm):

• T ≤ 10
• N ≤ ~10^3~

Subtask #2 (40 điểm):

• T ≤ 10
• N ≤ ~10^6~

Subtask #3 (30 điểm):

• ràng buộc gốc

Ví dụ:

NUMSWAPS.INP

4 
2 3 4 5

NUMSWAPS.OUT

0 2 2 0

Giải thích:

• Nếu N = 2 thì không chọn được cách nào cả vì có duy nhất 2 phần tử 1 2.
• Nếu N = 3 thì ta có 3 phần tử 1 2 3; cách thứ nhất giữ nguyên vị trí; cách thứ 2 đổi vị trí 1 cho 3 được dãy mới là 3 2 1 thỏa mãn 3 = 2+1.
• Nếu N = 4 thì ta có 4 phần tử là 1 2 3 4; cách thứ nhất đổi vị trí 2 cho 4 được dãy mới 1 4 3 2 thỏa mãn 1+4 = 3+2; Cách thức 2 là đổi vị trí 1 cho 3 ta được dãy mới là 3 2 1 4 thỏa mãn 3+2 =1+4.
• Nếu N = 5 thì không có được cách nào cả.