问题描述

设有 $N$ 个正整数（$1 ≤ N ≤ 50$），其中每一个均是大于等于 $1$、小于等于 $300$ 的数。 从这 $N$ 个数中任取出若干个数（不能取相邻的数），要求得到一种取法，使得到的和为最大。 例如：当 $N=5$ 时，有 $5$个数分别为：$13,18,28,45,21$； 此时，有许多种取法，如： $13,28,21$ 和为 $62$； $13, 45$ 和为 $58$； $18, 45$ 和为 $63$； $\dots$

输入格式

第一行是一个整数 $N$； 第二行有 $N$ 个符合条件的整数。

输出格式

一个整数，即最大和。

样例

输入

5
13 18 28 45 21

输出

63