문제

Note: The time limit for this problem is 3s, 1.5x the default.

FJ gave Bessie an array $a$ of length $N$ ($2\le N\le 500, -10^{15}\le a_i\le 10^{15}$) with all $\frac{N(N+1)}{2}$ contiguous subarray sums distinct. For each index $i\in [1,N]$, help Bessie compute the minimum amount it suffices to change $a_i$ by so that there are two different contiguous subarrays of $a$ with equal sum.

입력

The first line contains $N$.

The next line contains $a_1,\dots, a_N$ (the elements of $a$, in order).

출력

One line for each index $i\in [1,N]$.

예제 입력 1

2
2 -3

예제 출력 1

2
3

예제 입력 2

3
3 -10 4

예제 출력 2

1
6
1

점수

Input 3: $N\le 40$Input 4: $N \le 80$Inputs 5-7: $N \le 200$Inputs 8-16: No additional constraints.