#50Easy

Largest sum of neighbours

Time: 1 s · Memory: 256 MB

Loops

Statement

You are given $n$ integers. Among the sums of two adjacent numbers, find the largest one.

Input format

The first line contains $n$ ( $2 \le n \le 10^5$ ). The second line contains $n$ integers ( $|a_i| \le 10^9$ ).

Output format

A single integer — the largest sum of two neighbours.

Examples

Input

9
1 2 3 4 5 6 7 8 9

Output

Input

4
-5 -1 -8 -2

Output

-6

Note

An array is not required: keep the previous number in a separate variable and compare the sum with each new one. The starting maximum is the sum of the first pair, not $0$ (in the second example the answer is $-6$ ).

In the first example: $8 + 9 = 17$ .

Largest sum of neighbours

Time: 1 s · Memory: 256 MB

Loops

Statement

You are given $n$ integers. Among the sums of two adjacent numbers, find the largest one.

Input format

The first line contains $n$ ( $2 \le n \le 10^5$ ). The second line contains $n$ integers ( $|a_i| \le 10^9$ ).

Output format

A single integer — the largest sum of two neighbours.

Examples

Input

9
1 2 3 4 5 6 7 8 9

Output

Input

4
-5 -1 -8 -2

Output

-6

Note

In the first example: $8 + 9 = 17$ .