Description

小M幻想着有朝一日能成为金融大鳄，能够出任CEO迎娶白富美ahhh（咳咳咳…）。这不，他开始迷上了炒股。总所周知，股票交易市场可以通过买入和卖出来赚取利润。比如在某一时刻的市场报价是100元/股 买入，然后等到价格为108元/股的时候卖出，这样就可以赚到8元。

现在呢，小M在机缘巧合之下通过某种手段获得了股市的价格走势，即在t时刻的价格Rt（t=0，1，2，3，…，n-1）作为输入数据。那么为了获得最大利益，请帮助小M选择合适的买入和卖出时机，计算出价格差Rj- Ri(j>i)的最大值。如果不能够赚到钱（最大值≤0），小M可是会不高兴的，那么结果输出-1。那么聪明的你，能不能帮助小M走向人生巅峰呢？

Format

Input

第1行输入整数n。接下来输入n个整数Rt。（t=0，1，2，3，…，n-1）。（1≤Rt≤109，2≤n≤200000）

Output

在单独一行输出价格差Rj-Ri的最大值。

Samples

6
5 3 1 3 4 3

3

Hint