题目描述

小明看着眼前从左到右在一条线上的 n 座山峰，他想从中选出两座山峰，作为旅行的起点和终点，要求选出的较左边的山峰高度大于选出的较右边的山峰，定义这样选择后这次旅行的困难程度为两座山峰的高度差。问所有可能的选择方案中困难程度最大的方案的困难程度是多少，如果没有合法方案，答案为 0 。

输入格式

第一行为一个整数 n ，表示山峰的数目 ( 1 ≤ n ≤ $10^5$ )

第二行为 n 个空格隔开的整数 $a_i$ ，为每座山峰的高度 ( 1 ≤ $a_i$ ≤ $10^9$ )

数据范围

对于 60% 的数据， 1 ≤ n ≤ $10^3$

对于 100% 的数据， 1 ≤ n ≤ $10^5$

输出格式

一个整数，表示答案。

样例

4
1 5 3 9

2