题目背景

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

题目描述

给定一个整数序列 a1,a2,a3,...,an，每个 ai表示某只股票的在某一天的价格，请计算这只股票的最大回撤。即寻找两个下标满足1≤i≤j≤n，且 ai−aj最大。

注意，由于原油宝事件的出现，不能想当然地以为 ai一定是正数。

输入格式

第一行：单个整数表示 n，
第二行：n个整数表示a1,a2,a3,...,an。

输出格式

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

数据范围

对于 30% 的数据，n≤1000；

对于 60% 的数据，n≤10000；

对于 100% 的数据，1≤n≤100000，−100000≤ai≤100000。

样例数据

输入:

5

2 3 7 6 1

输出:

6

说明:

7-1=6

输入:

5

1 2 3 4 5

输出:

0

说明:

没有任何可能造成亏损的机会，所以是0

输入:

5

1 10 100 10 -100

输出:

200