Farmer John의 소들은 가장 좋아하는 동요 속 소처럼 달을 뛰어넘고 싶습니다. 안타깝게도 소는 뛸 수 없습니다.

지역 주술사가 이를 돕는 약 $P$개($1 \le P \le 150{,}000$)를 만들었습니다. 만든 순서대로 정확히 먹어야 하지만 일부는 건너뛸 수 있습니다.

각 약은 뛰는 능력을 높이는 ‘강도’($1 \le strength \le 500$)가 있습니다. 홀수 시간에 먹으면 점프가 늘고 짝수 시간에는 줄어듭니다. 약을 먹기 전 능력은 물론 0입니다.

어떤 약도 두 번 먹을 수 없습니다. 먹기 시작하면 시간1부터 매 시간 하나를 먹어야 합니다. 각 차례에 하나 이상의 약을 건너뛸 수 있습니다.

가장 높은 점프를 위해 먹을 약을 결정하세요.

입력

• $1$행: 정수 $P$.
• $2..P+1$행: 각 행은 약의 강도를 나타내는 정수입니다. 2행은 첫 약, 3행은 둘째 약이며 이후도 같습니다.

출력

• $1$행: 가능한 최대 점프를 나타내는 정수 하나.

예제

입력 1

8
7
2
1
8
4
3
5
6

출력 1

17