Cho dãy số nguyên \(A\ = \ (a_{1},\ a_{2},\ \ldots\ ,\ a_{n}).\) Với mỗi chỉ số 𝑥 (1 ≤ 𝑥 ≤ 𝑛), hãy tính C(𝑥) là số lượng những bộ ba chỉ số (𝑖, 𝑗, 𝑘) thỏa mãn hai điều kiện:

\[\left\{ \begin{array}{r} 1 \leq i < j < k < x \\ a_{i} + a_{j} + a_{k} = a_{x} \end{array} \right.\ \]

Dữ liệu vào:

+ Dòng 1 chứa số nguyên dương \(n\ \leq \ {5 \times 10}^{3}\)

+ Dòng 2 chứa \(n\) số nguyên \(a_{1},\ a_{2},\ \ldots\ ,\ a_{n}\) cách nhau bởi dấu cách \((\forall i:\ |a_{i}|\ \leq \ 10^{6})\)

Kết quả:

+ Một dòng \(n\ \)số nguyên: \(c(1),\ c(2),\ \ldots\ ,\ c(n)\), cách nhau bởi dấu cách.

Ràng buộc:

+ Subtask 1: Có 40% số test ứng với 40% số điểm của bài có \(n \leq 50.\)

+ Subtask 2: Có 30% số test ứng với 30% số điểm của bài có \(n \leq 500.\)

+ Subtask 3: Có 30% số test còn lại ứng với 30% số điểm của bài có \(n \leq 5000.\)

Ví dụ:

Input	Output	Giải thích
9 1 2 3 4 5 6 7 8 9	0 0 0 0 0 1 1 2 3	6 = 1 + 2 + 3 7 = 1 + 2 + 4 8 = 1 + 2 + 5 = 1 + 3 + 4 9 = 1 + 2 + 6 = 1 + 3 + 5 = 2 + 3 + 4
8 1 -1 1 -1 1 -1 1 -1	0 0 0 0 2 3 9 12