Background

小藤家的院子里有一排葡萄架，共 n 串葡萄，第 i 串葡萄的甜度为 a_i。

她想摘一些葡萄回来，但有个讲究：相邻的两串葡萄如果都被摘走，藤蔓会断，所以相邻的两串不能同时摘。

小藤希望摘到的葡萄总甜度尽量大。请求出最大总甜度。

Format

Input

第一行一个整数 n。 第二行 n 个整数 a_1, a_2, …, a_n。

Output

一行一个整数：最大总甜度。

Samples

5
3 4 3 4 3

9

样例说明 葡萄排成一排，相邻不能同摘。列举几种候选方案：

最优方案是摘第 1、3、5 串，总甜度为 3 + 3 + 3 = 9。

Limitation

1s, 1024KiB for each test case.

1 ≤ n ≤ 1000

1 ≤ a_i ≤ 1000