Купить и продать

Дана последовательность цен по дням. Купить можно в один день, продать — в любой более поздний.

Выведите наибольшую возможную разность «продал минус купил». Если любая сделка убыточна, ответ отрицательный: продать всё равно придётся.

В первой строке $n$ от $2$ до $2 \cdot 10^5$. Во второй — $n$ чисел, каждое по модулю не больше $10^9$.

Одно число.

Наивно — перебрать все пары «день покупки, день продажи»: $2 \cdot 10^{10}$ шагов. Достаточно одного прохода: идя слева направо, помните наименьшую цену из уже виденных. Разность здесь доходит до $2 \cdot 10^9$ — это меньше предела int ($2\,147\,483\,647$), но запаса всего семь процентов, и надёжнее сразу взять long long.