FJ đưa cho Bessie một mảng \(a\) có độ dài \(N(2\le N \le 500, -10^{15}\le a_i\le10^{15})\) với tất cả \(\frac{N*(N+1)}{2}\) dãy con liên tiếp đều có tổng đôi một khác nhau. Với mỗi chỉ số \(i\in[1,N]\) , hãy giúp Bessie tính lượng tối thiểu cần thay đổi với \(a_i\) sao cho có hai dãy con liền tiếp khác nhau có tổng bằng nhau.

Input

• Dòng đầu tiên chứa số \(N\).
• Dòng tiếp theo chứa \(a_1,a_2,...,a_N\)

Output

\(N\) dòng, dòng thứ \(i\) chứa lượng tối thiểu cần thay đổi với \(a_i\).

Scoring

• Subtask \(1\): \(N \leq 40\)
• Subtask \(2\): \(N \leq 80\)
• Subtask \(3\): \(N \leq 200\)
• Subtask \(4\): Không có điều kiện gì thêm.

Example

2
2 -3

2
3        

3
3 -10 4    

1
6
1