Трейдер наблюдает за ценой одной акции в течение n дней. В i-й день цена акции равна a_i.

Нужно выбрать два дня: день покупки i и более поздний день продажи j, где i < j, так, чтобы прибыль a_j - a_i была максимальной.

Обратите внимание, что если цена каждый день только падает, максимальная прибыль может оказаться отрицательной. Это означает, что трейдер всё равно обязан купить раньше и продать позже, даже если сделка будет убыточной.

Входные данные

В первой строке задано число n (2 <= n <= 2*10^5).

Во второй строке заданы n целых чисел a_i (-10^9 <= a_i <= 10^9) — цена акции по дням.

Выходные данные

Выведите одно целое число — максимальное значение a_j - a_i при условии i < j.

Ограничения

• 2 <= n <= 2*10^5
• -10^9 <= a_i <= 10^9
• ввод осуществляется через стандартный ввод
• вывод осуществляется через стандартный вывод

Примеры

Пример 1

Входные данные

2
5 3

Выходные данные

-2

Пример 2

Входные данные

3
-4 7 -2

Выходные данные

11