Саша Вилкин хочет кушать, так как уровень его сытости опустился до 0. По такому случаю он приходит в один из своих любимых ресторанов быстрого питания — «Лилка Вожка». Это заведение не зря стало его любимым, потому что как только он заходит внутрь, он попадает в новый мир, где еда работает совсем иначе...

Все блюда в этом чудесном месте обладают сытностью — неким целым числом. Если Саша съест какое-нибудь одно блюдо сытностью a, то его уровень сытости увеличится на a. В этом волшебном мире еда может и уменьшать уровень сытости (если сытность блюда отрицательна). К сожалению, желудок Саши не справляется, когда Саша ест много блюд подряд. Если он съедает несколько блюд с некоторыми сытностями, то каждое нечётное блюдо переваривается нормально, увеличивая сытость Саши на величину сытности этого блюда; но каждое чётное блюдо переваривается плохо, уменьшая сытость Саши на величину сытности этого блюда.

Изначально в ресторане находятся n блюд, которые лежат на стойке слева направо. Блюда пронумерованы числами от 1 до n в том порядке, в котором они лежат на стойке. Блюдо с номером i имеет сытность a_i. Саша слишком торопится, чтобы обдумывать свой выбор, поэтому он хочет просто купить несколько подряд идущих блюд (или не купить ни одного). Сделав выбор, Саша съест все купленные блюда слева направо в том порядке, в котором они лежат, и ничего больше есть не будет. Помогите Саше найти максимально возможный уровень его сытости после того, как он съест свой обед.

Более формально: есть последовательность целых чисел a_i. Нужно найти непрерывный отрезок последовательности (возможно, пустой), знакопеременная сумма которого максимальная. При этом первый элемент знакопеременной суммы всегда берётся со знаком плюс, независимо от его индекса.

В первой строке дается целое число n — количество блюд в ресторане (1 ≤ n ≤ 10⁵).

Во второй строке содержатся n целых чисел a_i, записанных через пробел — сытности блюд (−10⁵ ≤ a_i ≤ 10⁵).

Выведите единственное целое число — максимальный уровень сытости Саши после того, как он пообедает. Учтите, что Саша может ничего не съесть, чтобы остаться максимально сытым.

В первом примере Саше выгоднее всего просто съесть пятое блюдо, тогда уровень его сытости будет равен 5.

Во втором примере Саша может взять все блюда с первого по пятое, тогда знакопеременная сумма всех сытностей его блюд будет равна 15.

В третьем примере Саша может взять блюда с первого по четвёртое или со второе по пятое, тогда знакопеременная сумма всех сытностей блюд будет равна 2.