Doctor Livesey cares not only about the physical but also about the psychological state of the crew. To make the crew feel happier, the doctor decided to reduce the level of negativity. There are n people on the ship, and the mood of each can be described by an integer a_i.

Doctor Livesey does not yet have enough experience, so he can only improve the mood of one group of people. By choosing a subsegment of people, the doctor changes their mood to the opposite. Formally, this means that he selects two numbers 1 ≤ l ≤ r ≤ n and changes the signs of all values a_i on the segment [l; r].

The effectiveness of the team is determined by the mood of the most unhappy person, so the captain set the doctor the task of choosing such a segment of people that the minimum mood among all team members becomes as high as possible.

The first line of input contains a natural number n — the number of team members (1 ≤ n ≤ 10⁵).

The second line of input contains an array of integers a of length n — the mood of each team member, where a_i is the mood of the i-th person (−10⁹ ≤ a_i ≤ 10⁹). It is guaranteed that there exists at least one a_i < 0.

Output a single number — the highest possible value of the minimum mood in the team after the change.

In the first example, one can choose the segment [3; 4], then the moods of the people will be [−1, 3, 2, 4, 5].