Given an array of n integers a1, a2 ... an 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 am points (the am 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 a1, a2 ... an.

1 ≤ n ≤ 35

1 ≤ a_i ≤ 10⁶

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 are all odd.)