题目描述

股票价格瞬息万变。在金融市场上，经常需要统计一只股票的最大回撤。最大回撤是指投资者在某天买入、在之后某天卖出，可能造成的最大亏损，它可以反映一只股票在历史上的最坏表现。

给定整数序列 $a_1,a_2,a_3,\ldots,a_n$，每个 $a_i$ 表示某只股票在第 $i$ 天的价格。计算它的最大回撤，即寻找两个下标 $1\le i<j\le n$，使 $a_i-a_j$ 最大。若价格一直上涨，输出 0。

输入格式

第一行一个整数 $n$；第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

一行一个整数，表示这只股票的最大回撤。如果价格一直上涨，输出 0。

样例 1

输入

5
2 3 7 6 1

输出

6

样例 2

输入

6
1 2 3 4 5 5

输出

0

输入样例 #3

1
-8241

输出样例 #3

0

数据范围

60% 的数据：$1\le n\le1000$。全部数据：$1\le n\le100000$，$-100000\le a_i\le100000$。