Given an array of n integers a_1, a_2 ... a_n you can perform the following operation as many times as you want:

Pick a (contiguous) subarray that only contains odd integers or pick a (contiguous) subarray that only contains even integers, remove it from the array, forming a new array to perform the rest of your operations on, if the length of that subarray you removed is m you gain a_m points (the a_m from the original array before modification).

Find the maximum number of points you can gain applying after applying as many of these operations as you want.

Input

Your first line will contain a single integer n.

Your next line will contain n integers a_1, a_2 ... a_n.

1 ≤ n ≤ 35

1 ≤ a_i ≤ 10^6

Output

A single integer representing the maximum number of points you can get.

Example

Input
7
3 5 8 51 8 8 9

Output
60

Explanation

Delete three subarrays of size one, being the even numbers (8 then 8 then 8) gaining 3 + 3 + 3 points. Then delete the left over array (which is all odd).