당신의 보물 사냥꾼 팀은 귀금속과 귀중한 골동품으로 가득 찬 거대한 고고학 유적지를 발견했습니다. 이 유적지는 일직선상에 있는 $n$개의 발굴 지점으로 구성되어 있습니다.

초기 계획에 따르면 각 발굴 지점에는 순이익이 연관되어 있습니다. $i$번째 지점의 연관된 이익은 $p_i$입니다. 더 구체적으로, 이는 당신의 팀이 $i$번째 지점에서 1미터를 팔 때마다 $p_i$달러의 이익을 얻는다는 것을 의미합니다. $p_i$는 음수일 수도 있는데, 이는 굴착 기계의 운영 비용이 $i$번째 지점에서 발굴하여 얻는 실제 이익보다 크다는 것을 의미합니다.

당연히 당신은 가장 수익성이 높은 지점에서 최대한 많이 발굴하고 싶을 것입니다. 하지만 산사태를 방지하기 위해, 너무 가파른 경사를 만들어서는 안 됩니다. 더 정확히 말하면, 인접한 두 지점 사이의 발굴 깊이 차이는 1미터를 넘을 수 없습니다. 특히, 1번 지점과 $n$번 지점은 최대 1미터까지만 발굴할 수 있습니다.

이러한 조건 하에서 얻을 수 있는 최대 순이익은 얼마입니까?

예를 들어, 첫 번째 예제 입력의 경우 최적의 유효한 발굴 계획이 아래 그림에 나와 있습니다. 이 계획의 순이익은 8입니다.

입력

첫 번째 줄에는 양의 정수 $n$ ($1 \le n \le 250\,000$)이 주어집니다. 두 번째 줄에는 $n$개의 정수 $p_i$ ($-10^6 \le p_i \le 10^6$)가 공백으로 구분되어 주어집니다.

출력

얻을 수 있는 최대 이익인 정수 하나를 출력하십시오.

예제

입력 1

5
1 3 -4 2 1

출력 1

8

입력 2

4
1 1 -2 3

출력 2

5

입력 3

5
-1 -3 0 -5 -4

출력 3

0