Доктор Ливси заботится не только о физическом, но и о психологическом состоянии команды. Чтобы экипаж чувствовал себя счастливее, доктор решил снизить уровень негатива. На корабле находится n человек, и настроение каждого можно описать целым числом a_i.

Доктор Ливси пока не обладает достаточным опытом, поэтому он может улучшить настроение только одной группе людей. Выбрав подотрезок людей, доктор изменяет их настроение на противоположное. Формально это означает, что он выбирает два числа 1 ≤ l ≤ r ≤ n и меняет знаки всех значений a_i на отрезке [l; r].

Эффективность команды определяется настроением самого несчастного человека, поэтому капитан поставил перед доктором задачу: выбрать такой отрезок людей, чтобы минимальное настроение среди всех членов команды стало как можно выше.

В первой строке входных данных вводится натуральное число n — количество членов команды (1 ≤ n ≤ 10⁵).

Во второй строке входных данных вводится массив целых чисел a длины n — настроения каждого члена в команде, где a_i — настроение i-го человека (−10⁹ ≤ a_i ≤ 10⁹). Гарантируется, что существует a_i < 0.

Выведите одно число — наибольшее возможное значение минимального настроения в команде после изменения.

В первом примере можно выбрать отрезок [3; 4], тогда настроения людей будут [−1, 3, 2, 4, 5].