이 문제의 시간 제한은 기본 시간 제한의 \(1.5\)배인 \(3\)초이다.

존은 베시에게 길이가 \(N\)인 배열 \(a\)를 주었다. \((2 \le N \le 500, -10^{15} \le a_i \le 10^{15})\) 이 배열의 연속 부분 배열 \(\frac{N(N+1)}{2}\)개의 합은 모두 서로 다르다.

각 인덱스 \(i \in [1,N]\)에 대하여, \(a_i\)의 값만 변경하여 서로 다른 두 연속 부분 배열의 합이 같아지도록 하려고 한다. 이때 가능한 변경량의 절댓값 중 최솟값을 구하여라.

입력

첫째 줄에 \(N\)이 주어진다.

둘째 줄에 배열의 원소 \(a_1,a_2,\dots,a_N\)이 순서대로 주어진다.

출력

각 인덱스 \(i \in [1,N]\)에 대한 답을 한 줄에 하나씩 출력한다.

예제 입력 1

2
2 -3

예제 출력 1

2
3

예제 설명 1

\(a_1\)을 \(2\)만큼 감소시키면 \(a_1+a_2=a_2\)가 된다. 마찬가지로 \(a_2\)를 \(3\)만큼 증가시키면 \(a_1+a_2=a_1\)이 된다.

예제 입력 2

3
3 -10 4

예제 출력 2

1
6
1

예제 설명 2

\(a_1\)을 \(1\)만큼 증가시키거나 \(a_3\)을 \(1\)만큼 감소시키면 \(a_1=a_3\)이 된다. \(a_2\)를 \(6\)만큼 증가시키면 \(a_1=a_1+a_2+a_3\)이 된다.

출처

USACO 2023 February Contest, Gold, Problem 1. Equal Sum Subarrays