설명
어느 집에 살고 있는 알파카는 수중에서 한 쌍을 골라 다음과 같은 연산으로 빼고 싶다.
수들 수열을 A라고 할때,
\(A_i=A_j-(i-j)\)
을 실행한후,
갱신된 A_i의 값을 \(A_i'\), 원래 값을 \(A_i\)라 할때,
\(A_j=A_i'+A_i+((i-j)A_i'A_i)\)
을 실행 한다.
이때, \(A\)의 원소의 합의 절댓값이 최소한이 되게 하여라, (단, \(1 \le i < j \le N\)이다.)
\(N\)은 수열 \(A\)의 길이이다.
단, 최소한 한쌍 이상을 골라야 한다.
제약
\(2 \le N \le 5000\)
\(-10^9 \le A_i(1 \le i \le N) \le 10^9\)
입력 형식
첫번째 줄에 \(N\)을 입력 받는다.
두번째 줄 부터 \(A\)의 원소들을 입력 받는다.
출력 형식
첫째 줄에 \(A\)의 원소의 합을 출력한다.
만약에 \(A\)의 원소의 합이 2개가 될 경우, 비 내림차순으로 \(A\)의 원소의 합을 공백으로 구분해서 출력하라.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 40점 | \(A\)의 모든 원소의 합은 0이다. |
2 | 20점 | \(N \le 10\) |
3 | 40점 | 추가 제한 없음. |
예제 1
입력
10
-3 4 -5 -3 -9 2 -5 6 2 -6
출력
1
문제 정보
HyunwooAlpaca 작성
출처 지정되지 않음