题目背景

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

题目描述

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

输入格式

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

输出格式

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

5
2 3 7 6 1

6

5
1 2 3 4 5

0

数据范围

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

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

对于100%的数据,$1≤n≤100000，1≤ai≤100000$；