题目描述

给定一个整数序列 $a_1, a_2, a_3, \cdots, a_n$，每个 $a_i$ 表示同一只股票的在某一天的价格，请计算这只股票的最大回撤。即寻找两个下标满足 $1\leq i\leq j\leq n$，且 $a_i-a_j$最大。

输入格式

第一行：单个整数表示 $n$， 第二行：$n$ 个整数表示 $a_1, a_2, a_3, \cdots, a_n$。

输出格式

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

数据范围

• 对于 $30\%$ 的数据，$n\leq 1000$；
• 对于 $60\%$ 的数据，$n\leq 10000$；
• 对于 $100\%$ 的数据，$1\leq n\leq 100000$，$-100000\leq a_i\leq 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