Mixing two solutions

Time limit1sMemory limit512 MB

Summary

Given a sorted array of N integers, choose two different elements whose sum is closest to 0, breaking ties toward the smaller (negative) sum.

Level: Medium5 of 10
Topics: Two pointers, Sorting, Array
Solved: No attempts yet

Problem

A chemistry lab keeps many kinds of liquid solutions. Every solution carries one characteristic value between -100,000,000 and 100,000,000. When you mix equal amounts of two solutions, the characteristic value of the result is the sum of the two values.

Each solution sits in its own 10ml test tube holding 10ml, and there is exactly one empty 20ml test tube. You cannot measure out a partial amount, so the only possible mixture pours 10ml of one solution and 10ml of another into the 20ml tube, and you may do it once. You therefore read the characteristic values first and decide which two solutions to mix.

For example, take five solutions with characteristic values -101, -3, -1, 5, 93. Mixing the solution of value -101 with the one of value 93 gives -8, and mixing 5 with 93 gives 98. Over all possible pairs, the value 2 is the one closest to 0.

The characteristic values $A_1, \ldots, A_N$ are given in non decreasing order. Find the value $B$ closest to 0 that you can make by mixing two different solutions.

Input

N
A1 A2 … AN

The first line has the number of solutions $N$ . The second line has the $N$ characteristic values in non decreasing order, separated by single spaces.

Output

Print the characteristic value $B$ closest to 0 on one line. If two reachable values sit at the same distance from 0, print the smaller one, which is the negative one.

Constraints

2 ≤ N ≤ 100,000
-100,000,000 ≤ Ai ≤ 100,000,000
$A_{i-1} \le A_i$ (2 ≤ i ≤ N)

Examples3

Example 1
Input
```
5
-101 -3 -1 5 93
```
Expected output
```
2
```
Example 2
Input
```
2
-100000 -99999
```
Expected output
```
-199999
```
Example 3
Input
```
7
-698 -332 -123 54 531 535 699
```
Expected output
```
1
```