[USACO23FEB] Equal Sum Subarrays G

**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 $\dfrac{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 ai by so that there are two different contiguous subarrays of a with equal sum. ## Input The first line contains $N$. The next line contains $a_1, \cdots ,a_N$ (the elements of $a$, in order). ## Output One line for each index $i \in [1,N]$. [samples] ## Note ### Explanation for Sample 1 Decreasing $a_1$ by $2$ would result in $a_1+a_2=a_2$. Similarly, increasing $a_2$ by $3$ would result in $a_1+a_2=a_1$. ### Explanation for Sample 2 Increasing a1 or decreasing $a_3$ by $1$ would result in $a_1=a_3$. Increasing $a_2$ by $6$ would result in $a_1=a_1+a_2+a_3$. ### SCORING - Input $3$: $N \le 40$ - Input $4$: $N \le 80$ - Inputs $5-7$: $N \le 200$ - Inputs 8-16: No additional constraints.