시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB258967635.681%

문제

길이 $N$의 수열 $A$에 대해 함수 $f(l,r)$은

$$f(l,r) =\sum_{i = l}^{r} (-1)^{\,i - l} A_i$$

로 정의된다.

$(1 \le l \le r \le N)$을 만족하는 모든 정수 순서쌍 $(l,r)$에 대하여 $f(l,r)$의 최댓값을 구하여라.

입력

첫째 줄에 $N$이 주어진다. $(1 \le N \le 200\,000)$

둘째 줄에 $N$개의 정수 $A_1, A_2, \ldots, A_N$이 공백으로 구분되어 주어진다. $(-10^9 \le A_i \le 10^9)$

출력

첫째 줄에 $f(l,r)$의 최댓값을 출력한다.

예제 입력 1

5
-1 2 -4 -2 3

예제 출력 1

6