题目描述

给定一个长为 $n$ 的序列 $a$，你可以进行一次操作，将这个序列的一个连续子区间的所有数同时增加一个相同的整数（无大小要求），请你求出修改后这个序列极差的最小值。

一个序列的极差被定义为最大值减去最小值。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个正整数表示序列 $a$。

输出格式

输出一行一个非负整数表示答案。

输入输出样例 #1

输入 #1

5
5 7 14 2 8

输出 #1

6

输入输出样例 #2

输入 #2

6
2 14 9 1 7 4

输出 #2

6

说明/提示

对于所有数据，保证 $1 \le n \le 10^6,1 \le a_i \le 10^9$。

本题采用捆绑测试计分。