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

Background

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

Description

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

Format

Input

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

Output

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

Samples

5
2 3 7 6 1 

6

Limitation

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