Note: The time limit for this problem is 3s, 1.5x the default.
FJ gave Bessie an array a of length N (2≤N≤500,−1015≤ai≤1015) with all N(N+1)2 contiguous subarray sums distinct. For each index i∈[1,N], help Bessie compute the minimum amount it suffices to change ai by so that there are two different contiguous subarrays of a with equal sum.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N.
The next line contains a1,…,aN (the elements of a, in order).
OUTPUT FORMAT (print output to the terminal / stdout):
One line for each index i∈[1,N].
SAMPLE INPUT:
2
2 -3
SAMPLE OUTPUT:
2
3
Decreasing a1 by 2 would result in a1+a2=a2. Similarly, increasing a2 by 3 would result in a1+a2=a1.
SAMPLE INPUT:
3
3 -10 4
SAMPLE OUTPUT:
1
6
1
Increasing a1 or decreasing a3 by 1 would result in a1=a3. Increasing a2 by 6 would result in a1=a1+a2+a3.
SCORING:
Input 3: N≤40
Input 4: N≤80
Inputs 5-7: N≤200
Inputs 8-16: No additional constraints.
Problem credits: Benjamin Qi