[USACO23FEB] Equal Sum Subarrays G

### 题目描述 **提示：本题的时间限制是3s，为默认值的1.5倍。** FJ给了Bessie一个长度为 $N(2\leq N\leq 500, -10^{15}\leq a_i \leq 10^{15})$ 的数组，且数组所有的 $\frac{N(N+1)}{2}$ 个区间和互不相同。对于每个 $i\in[1,N]$，帮助Bessie把 $a_i$ 改成一个值，使得数组有两个区间和相等，且改值与 $a_i$ 的差值最小。 ### 输入格式 第一行输入 $N$。 第二行输入数组 $a$。 ### 输出格式 对于每个 $i\in[1,N]$，每行输出满足题意的最小差值。 ### 说明/提示 样例1：把 $a_1$减 $2$ 使得 $a_1+a_2=a_2$。类似的，把 $a_2$加 $3$ 使得 $a_1+a_2=a_1$。 样例2：把 $a_1$ 加 $1$ 或把 $a_3$ 减 $1$ 使得 $a_1=a_3$。把 $a_2$ 加 $6$ 使得 $a_1=a_1+a_2+a_3$。 数据范围 输入 $3$：$N\leq 40$ 输入 $4$：$N\leq 80$ 输入 $5-7$：$N\leq 200$ 输入 $8-16$：没有额外限制。

**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.

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

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

2
2 -3

2
3

3
3 -10 4

1
6
1

### 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.