해커

해커 바이트아사르가 올해 국제 해킹 올림피아드에 출전한다. 종목 하나는 시스템 관리자와 벌이는 게임이다. 컴퓨터 $n$대가 1번부터 $n$번까지 번호를 달고 고리 모양으로 연결되어 있다. $i = 1, \ldots, n-1$에 대해 $i$번과 $i+1$번이 연결되어 있고, $n$번과 1번도 연결되어 있다.

게임 규칙은 다음과 같다.

• 바이트아사르가 먼저 움직이고, 그다음부터 관리자와 바이트아사르가 번갈아 움직인다.
• 첫 수에서 바이트아사르는 컴퓨터 하나를 골라 해킹한다.
• 첫 수에서 관리자는 해킹되지 않은 컴퓨터 하나를 골라 보호한다.
• 이후의 수에서 바이트아사르는 아무것도 하지 않거나, 해킹되지도 보호되지도 않았으면서 이미 해킹된 컴퓨터와 직접 연결된 컴퓨터를 골라 해킹한다.
• 이후의 수에서 관리자는 아무것도 하지 않거나, 해킹되지도 보호되지도 않았으면서 이미 보호된 컴퓨터와 직접 연결된 컴퓨터를 골라 보호한다.
• 두 사람이 연속한 두 수에서 모두 아무것도 하지 않으면 게임이 끝난다.

게임을 시작할 때는 해킹되거나 보호된 컴퓨터가 없다. $i$번 컴퓨터에는 가치가 $v_i$인 자료가 들어 있고, 바이트아사르는 해킹한 컴퓨터마다 그 가치 $v_i$를 점수로 얻는다. 관리자가 최선으로 막을 때 바이트아사르가 얻을 수 있는 최대 점수를 구하라.

첫째 줄에 컴퓨터의 수 $n$이 주어진다. ($2 \le n \le 50\,000$)

둘째 줄에 정수 $v_1, v_2, \ldots, v_n$이 공백으로 구분되어 주어진다. $v_i$는 $i$번 컴퓨터에 저장된 자료의 가치다. ($1 \le v_i \le 2000$)

관리자가 최선으로 움직일 때 바이트아사르가 얻는 최대 점수를 한 줄에 출력한다.

첫 번째 예제에서 바이트아사르는 2번 컴퓨터를 해킹해 6점을 얻는다. 관리자는 3번 컴퓨터를 보호한다. 이어서 바이트아사르가 1번 컴퓨터를 해킹해 7점을 얻고, 마지막으로 관리자가 4번 컴퓨터를 보호한다.