당신은 $n$일 동안 적절히 게임을 하여 행복 지수를 최대한으로 얻으려고 한다. $i$번째 날에 게임을 한다면 $D_i$의 행복 지수를 얻을 수 있다.

하지만, 당신은 한번 게임을 하면 열정적으로 게임을 하기 때문에 휴식이 필요하다. 구체적으로 $i$번째 날에 게임을 한 경우 $i+1$번째 날에는 쉬어야 한다.

물론, 전날에 게임을 하지 않았더라도 자유롭게 쉴 수 있다. 각 날에 대한 행복 지수가 주어졌을 때, 당신이 얻을 수 있는 최대한의 행복 지수를 구해보자.

첫째 줄에 일 수 $n$이 주어진다. $(1 ≤ n ≤ 100,000)$

둘째 줄에 $D_1, D_2, ... , D_n$이 공백으로 구분되어 주어진다. $(1 ≤ D_i ≤ 10,000)$