该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

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

题目描述

给定一个整数序列 $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。

5
2 3 7 6 1

6

样例解释 1

7-1=6

5
1 2 3 4 5

0

样例解释 2

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

5
1 10 100 10 -100

200

数据范围

• 对于 $30\%$ 的数据，$n\leq 1000$；
• 对于 $60\%$ 的数据，$n\leq 10000$；
• 对于 $100\%$ 的数据，$1\leq n\leq 100000$，$-100000\leq a_i\leq 100000$。