题目描述

薯条哥有一个长度为$n$的数组，他想要选择一个下标$i(1\le i\le n)$，随后，将$a_i$及其左边元素全部染红，$a_i$右边的元素全部染蓝，使得红色元素的极差和蓝色元素的极差的差的绝对值最小，请你直接输出这个值。

极差是指数组中最大值和最小值的差。

输入描述

第一行输入一个整数$n(2\le n\le 10^5)$代表数组的长度。

第二行$n$个整数$a_1,a_2,...,a_n(1\le a_i\le 10^9)$代表数组的元素。

输出描述

在一行上输出一个正整数，表示红色元素的极差和蓝色元素的极差的差的绝对值的最小值。

样例

输入

5
1 2 4 3 5

输出

1