Equal Sum Subarrays

문제

FJ gave Bessie an array $aa$ of length $NN$ ($2\le N\le 500,-{10}^{15}\le a_i\le {10}^{15}2\backslash le\; N\backslash le\; 500,\; -10^\{15\}\backslash le\; a\_i\backslash le\; 10^\{15\}$) with all $\frac{N(N+1)}{2}\backslash frac\{N(N+1)\}\{2\}$ contiguous subarray sums distinct. For each index $i\in [1,N]i\backslash in\; [1,N]$, help Bessie compute the minimum amount it suffices to change $a_{i}a\_i$ by so that there are two different contiguous subarrays of $aa$ with equal sum.

입력

The first line contains $NN$.

The next line contains $a_1,\dots ,a_{N}a\_1,\backslash dots,\; a\_N$ (the elements of $aa$, in order).

출력

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