뒤집기

철수와 영희는 $N$번의 게임을 했다. 각 게임의 결과는 정수 하나이다. 한번의 게임에서 철수가 이기면 그 결과는 양수, 영희가 이기면 그 결과는 음수, 비기면 그 결과는 $0$이다. $N$번의 게임의 결과가 게임을 한 순서대로 $N$개의 정수로 저장되어 있다.

철수는 게임의 기록이 잘못 저장되어 있을 수 있다는 것을 알았다. 기록의 저장이 잘못된 방법은 게임 결과의 연속된 $K$개($0 \le K \le N$)가 부호가 바뀐 것이다. 철수는 주어진 기록에서 잘못된 것을 수정했을때 얻을 수 있는 가장 큰 점수 합을 알고 싶다.

예를 들어, 저장된 정수들이 $-1$, $3$, $-2$, $-4$, $1$, $-5$, $3$이라면 중간의 $-2$, $-4$, $1$, $-5$의 부호를 바꾸어 $-1$, $3$, $2$, $4$, $-1$, $5$, $3$으로 수정하면 가장 큰 합인 $15$를 얻을 수 있다.

$N$번의 게임 결과를 입력으로 받아 가능한 모든 수정 방법 중 가장 큰 점수를 얻을 수 있는 것을 계산하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 그려지는 정수의 개수를 나타내는 자연수 $N$($1 \le N \le 1\,000\,000$)이 주어진다.

다음 줄에 $N$개 정수가 게임을 한 순서대로 주어진다. 주어지는 값들은 $-1\,000$ 이상 $1\,000$이하이다.

출력 형식

가능한 모든 수정 방법으로 만들 수 있는 점수들 중 가장 큰 점수를 출력한다.

예제 1

7
-1 3 -2 -4 1 -5 3

15

예제 2

5
1 2 3 4 5

15

채점 방식

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

해설