감속 점프

한 선수가 사방치기와 세단뛰기를 섞은 새로운 스포츠에 참가한다. 이 종목에서는 $n$개의 사각형이 지면에 일정한 간격으로 한 줄로 놓여 있다. 첫 단계는 도움닫기로, 선수는 첫 번째 사각형을 향해 달려가서 그곳에서 첫 점프를 시작한다. 그다음에는 임의의 개수의 다른 사각형에 착지할 수 있으며, 마지막 사각형에 반드시 착지해야 한다.

심사위원은 각 사각형에 점프할 때 얻는 점수를 미리 정해 두었고, 선수의 점수는 처음과 마지막 사각형을 포함해 착지한 모든 사각형의 점수 합이다.

이 종목의 특성상 선수는 점프를 시작한 뒤에는 더 이상 가속할 수 없고, 연속한 점프의 길이는 절대 늘어날 수 없다. 방향을 되돌리는 것도 당연히 불가능하다.

각 사각형에 심사위원이 부여한 점수가 주어질 때, 이 종목에서 선수가 얻을 수 있는 최대 점수를 구하라.

입력은 다음과 같다.

• 한 줄에 정수 $n$ ($2\leq n\leq 3000$), 즉 사각형의 개수.
• 한 줄에 $n$개의 정수 $p_1, p_2, \dots, p_n$ ($-10^9\leq p_i\leq 10^9$), 즉 각 사각형에 점프할 때 심사위원이 부여하는 점수.

선수가 얻을 수 있는 최대 점수를 출력하라.