뒤집기

$N$ 명의 선수가 좌우 일렬로 서 있다. 왼쪽에서 $i$ 번째 선수의 실력은 $A_i$이다.

당신은 이 선수 중에서 좌우로 연속한 선수들을 한 명 이상 선발하여 실력의 합이 가장 큰 팀을 구성하려고 한다.

당신은 선수들을 선발하기 직전에 단 한 번 좌우로 연속한 선수들의 순서를 뒤집을 수 있다. 순서를 뒤집는다는 것의 의미는 $1$ 이상 $N$ 이하인 정수 $i$와 $j$를 정해서 $i$ 번째 선수부터 $j$ 번째 선수까지 총 $|j-i|+1$ 명의 선수들의 좌우 순서가 반대가 되도록 하는 것이다. 만약 $i = j$인 경우, 뒤집는 것은 아무 효과가 없다. 즉, 뒤집지 않는 것과 같은 효과이다.

예를 들어, $N = 4$이고 선수들의 실력이 순서대로 $2, -1, 3, -1$이라고 하자. 이 경우, $i = 1$, $j = 2$로 정해서 뒤집기를 하고 나면 선수들의 실력은 왼쪽부터 $-1, 2, 3, -1$이 되고, 이때 실력의 합이 가장 큰 팀을 구성하는 방법은 두 번째부터 세 번째까지의 선수들을 선발하는 것이다. 이 경우, 실력의 합은 $2 + 3 = 5$이다.

입력 형식

첫 줄에 선수들의 수를 나타내는 정수 $N$이 주어진다. ($1 \le N \le 1\,000\,000$)

두 번째 줄에 선수들의 실력을 나타내는 $N$ 개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. ($-1\,000\,000\,000 \le A_i \le 1\,000\,000\,000$)

출력 형식

좌우로 연속한 선수들의 순서를 적절히 뒤집어 실력의 합이 가장 큰 팀을 구성할 때, 그 팀의 실력 합을 나타내는 정수를 출력한다.

예제 1

4
2 -1 3 -1

5

예제 2

3
-1 3 -1

3

예제 3

5
2 -1 3 -2 5

9

예제 4

4
-2 -1 -3 -1

-1

예제 설명

예제 2에서, 뒤집는 방법과 상관없이 실력이 $3$인 선수 한 명을 선발하여 팀을 구성해야 팀의 실력 합이 최대가 된다.

예제 3에서, $i = 4$, $j = 5$로 뒤집기를 하여, 선수들의 실력이 왼쪽부터 $2, -1, 3, 5, -2$가 되도록 한 후, 첫 번째부터 네 번째까지의 선수들을 선발하여 팀을 구성하면 실력의 합이 $9$가 된다.

예제 4에서, 뒤집는 방법과 상관없이 실력이 $-1$인 선수 한 명을 선발하여 팀을 구성해야 팀의 실력 합이 최대가 된다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설