Problem 5C. 旋转数组

时间限制：1s

空间限制：256MB

Description

小季有一个数组 \(a_1, a_2, ..., a_n\) ，他将对该数组执行一次以下操作：

• 选取此数组的一个子序列，并将其循环旋转任意次数。

即，他只可以做一次以下操作：

• 选取两个整数 \(l\) 和 \(r\) ，使得 \(1 \le l \le r \le n\) ，和一个任意正整数 k。
• 重复 \(k\) 次下面的操作：设置 \(a_l=a_{l+1}, a_{l+1}=a_{l+2},...,a_{r-1}=a_r,a_r=a_l\) 。（同时改变）

小季希望最大化 \(a_n−a_1\) 的值，在恰好一次这样的操作之后。确定他可以获得的 \(a_n-a_1\) 的最大值。

Input Format

第一行输入一个整数 \( n (1 \le n \le 10^5)\) ,表示数组长度。

接下来的一行含有 \(n\) 个整数 \(a_i (1 \le a_i \le 10^5)\) ，表示该数组。

Output Format

输出包含一行一个整数，表示最大的 \(a_n - a_1\) 。

Input Example #1：

6
1 3 9 11 5 7

Output Example #1：

10

Input Example #2：

1
20

Output Example #2：

0