Cho số nguyên dương N và dãy số nguyên ~a_1, a_2, a_3,…, a_N~.

Yêu cầu:

• Với mỗi chỉ số ~x~ ~(1\le x\le N)~, hãy tính ~c\left(x\right)~ là số lượng những bộ ba chỉ số ~\left(i,\ j,\ k\right)~ thỏa mãn đồng thời hai điều kiện:
  • ~1 ≤ i < j < k < x~ (~i, j, k, x~ là những số nguyên dương)
  • ~a_i + a_j + a_k = a_x~

Ví dụ: Cho ~N=5~ dãy gồm ~5~ phần tử: ~\{-5; 7; 6; -5; 8\}~, với các chỉ số ~x = 1, 2, 3, 4~ không có bộ ba (~i, j, k~) nào thỏa mãn nên ~c(1) = 0~, ~c(2) = 0~, ~c(3) = 0~, ~c(4) = 0~, với chỉ số ~x = 5~ có ~a_5 = a_1 + a_2 + a_3 = -5 + 7 + 6 = 8, a_5 = a_2 + a_3 + a_4 = 7 + 6 + (-5) = 8~ nên ~c(5) = 2~.

INPUT

Đọc từ bàn phím theo cấu trúc sau:

• Dòng thứ nhất chứa số nguyên dương ~N~ ~(1 \le N \le5000)~;
• Dòng thứ hai chứa ~N~ số nguyên ~a_1,a_2,\ldots,a_N~ ~(\left|a_i\right|\le{10}^6, 1 ≤ i ≤ N)~.

OUTPUT

• Xuất ra màn hình một dòng duy nhất gồm ~N~ số nguyên ~c(1), c(2), …, c(N)~. Các số trên cùng một dòng ghi cách nhau bởi một dấu cách.

SAMPLE INPUT 1

8
-4 2 -2 3 0 -2 -1 1

SAMPLE OUTPUT 1

0 0 0 0 0 1 2 4

Giải thích:

• ~N = 5~, ~K = 10~, dãy ~\{1; 2; 3; 4; 5\}~ có các dãy con liên tiếp kề nhau có độ dài ~L = 2~ là ~\{1; 2\}~, ~\{2; 3\}~, ~\{3; 4\}~, ~\{4; 5\}~ đều có tổng các phần tử bé hơn ~K~, các dãy con liên tiếp kề nhau có độ dài ~L = 3~ là ~\{1; 2; 3\}~, ~\{2; 3; 4\}~, ~\{3; 4; 5\}~ trong đó có dãy con ~\{3; 4; 5\}~ có tổng các phần tử lớn hơn ~K~ nên ~L = 3~ không thỏa mãn yêu cầu bài toán, vậy ~L = 2~ thỏa mãn yêu cầu bài toán.

SUBTASKS

• ~30\%~ số điểm của bài ứng với các bộ dữ liệu vào có giới hạn ~\mathrm{1\ \le\ N\ \le\ 50}~;
• ~20\%~ số điểm của bài ứng với các bộ dữ liệu vào có giới hạn ~\mathrm{50\ <\ N\ \le\ 500}~;
• ~50\%~ số điểm của bài ứng với các bộ dữ liệu vào có giới hạn ~\mathrm{500\ <\ N\ \le\ 5000}~.