Robber Problem

Time Limit	Memory	Input	Output
1 s	64 MB	stdin	stdout

Time Limit

Memory

Input

Output

1 s

64 MB

stdin

stdout

A robber is planning to rob houses along a street. Each house has a certain amount of money stashed inside. The only thing stopping him from robbing all of them is that the houses have connected security systems: if two adjacent houses are robbed on the same night, the alarm will automatically go off.

Write a program that determines the largest amount of money the robber can steal without triggering the alarm. Formally, find the largest sum of a subsequence of the given sequence that does not contain two consecutive elements.

Input

First line of input will be a single number $n$ , the number of houses.
In the next line will be $n$ numbers $a_{1}, a_{2}, \dots, a_{n}$ , the amount of money in each house.

Output

A single number - the largest amount of money that can be stolen.

Example

Input

5
2 7 9 3 1

Output

The robber robs the houses with $2$ , $9$ and $1$ ( $2 + 9 + 1 = 12$ ). No two of them are adjacent.

Constraints

$1 \leq n \leq 2 \cdot 1 0^{5}$
$0 \leq a_{i} \leq 1 0^{9}$

Time Limit	Memory	Input	Output
1 s	64 MB	stdin	stdout

Input

First line of input will be a single number $n$ , the number of houses.
In the next line will be $n$ numbers $a_{1}, a_{2}, \dots, a_{n}$ , the amount of money in each house.

Output

A single number - the largest amount of money that can be stolen.

Example

Input

5
2 7 9 3 1

Output

The robber robs the houses with $2$ , $9$ and $1$ ( $2 + 9 + 1 = 12$ ). No two of them are adjacent.

Constraints

$1 \leq n \leq 2 \cdot 1 0^{5}$
$0 \leq a_{i} \leq 1 0^{9}$

Robber Problem

Input

Output

Example

Constraints

Submit your solution

Robber Problem

Input

Output

Example

Constraints

Submit your solution