Minimum Change to Create Subarray Sum Collision

FJ gives Bessie an array \(a\) of length \(N\) (\(2\le N\le500\), \( -10^{15} \le a_i \le 10^{15}\)) with all \(\frac{N(N+1)}{2}\) contiguous subarray sums distinct. For each index \(i\) (1-indexed), Bessie wants to know the minimum amount by which \(a_i\) needs to be changed (increased or decreased) so that in the new array there exist two different contiguous subarrays having equal sum.

Formally, let the original array be \(a = [a_1,a_2,\dots,a_N]\) and its prefix sums be \(P[0]=0\) and \(P[i]=a_1+\cdots+a_i\) for \(1\le i\le N\). For any contiguous subarray \([L,R]\) the sum is \(S(L,R)=P[R]-P[L-1]\). Initially all these sums are distinct. Now, for a fixed index \(i\), suppose we change \(a_i\) to \(a_i+\delta\) (and leave other entries unchanged). Then any subarray that includes index \(i\) will have its sum increased by \(\delta\) while any subarray that does not include index \(i\) remains unchanged. We wish to choose a nonzero \(\delta\) such that there exists a pair of contiguous subarrays, one including \(i\) and one not including \(i\), which have equal sum in the modified array. That is, we need to have:

[ S(L_1,R_1) + \delta = S(L_2,R_2) ]

where \(L_1\le i\le R_1\) and \(i\notin [L_2,R_2]\). Equivalently, \(\delta = S(L_2,R_2)-S(L_1,R_1)\). Among all such possibilities, output the minimum possible \(|\delta|\>.

Note: The time limit for this problem is 3 seconds, which is 1.5 times the default.

inputFormat

The first line contains a single integer \(N\). The second line contains \(N\) space‐separated integers, representing the array \(a_1, a_2, \ldots, a_N\). It is guaranteed that all contiguous subarray sums of \(a\) are distinct.

outputFormat

Output \(N\) space‐separated integers, where the \(i\)th integer is the minimum absolute change required for \(a_i\) so that after the change there exist two different contiguous subarrays with equal sum.

sample

2
1 2

1 1