[R37B]生日蛋糕 - 代码源竞赛平台

时空限制

1S/512M

题目描述

Tom 为了给朋友 Boris 庆祝生日，买了一个生日蛋糕，由于切蛋糕机器故障，将整块生日蛋糕切成了 $n$ 个大小不相等的小蛋糕，Tom 将它们排成一排，第 $i$ 个小蛋糕的大小为 $a_i$。

Tom 决定从切成的这些蛋糕中选取连续一段蛋糕（至少选两个）用来在生日派对上发给朋友们（剩下的自己偷偷留着吃^_^），他会将其中最大的那块分给 Boris，为了让 Boris 开心，他希望 Boris 的蛋糕大小比较突出，因此他希望他选取的蛋糕中最大的蛋糕的大小与第二大的蛋糕的大小的差尽量大，请你帮他找到这个最大值。

输入格式

第一行包含一个整数 $n$，表示整块生日蛋糕切成的小蛋糕的个数。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示每块小蛋糕的大小。

输出格式

输出一行一个整数，表示选取的蛋糕中最大的蛋糕的大小与第二大的蛋糕的大小的差的最大值。

样例

样例输入 1

5
6 1 4 2 7

样例输出 1

5

样例输入 2

10
1 8 11 2 13 5 6 4 9 14

样例输出 2

11

数据范围

对于 $100\%$ 的数据，$2 \le n \le 100$，$1 \le a_i \le 10^9$，保证 $a_i$ 互不相同。