## USACO 2023 February Contest, Gold

## Problem 1. Equal Sum Subarrays

Contest has ended.

**Log in to allow submissions in analysis mode**

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

#### INPUT FORMAT (input arrives from the terminal / stdin):

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

#### OUTPUT FORMAT (print output to the terminal / stdout):

One line for each index $i\in [1,N]$.#### SAMPLE INPUT:

2 2 -3

#### SAMPLE OUTPUT:

2 3

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

#### SAMPLE INPUT:

3 3 -10 4

#### SAMPLE OUTPUT:

1 6 1

Increasing $a_1$ 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.

Problem credits: Benjamin Qi