B. Array Stabilization_ou are given an array aa consisting of nn integer

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array aa consisting of nn integer numbers.

Let instability of the array be the following value: maxi=1nai−mini=1naimaxi=1nai−mini=1nai.

You have to remove exactly one element from this array to minimize instability of the resulting (n−1)(n−1)-elements array. Your task is to calculate the minimum possible instability.

Input

The first line of the input contains one integer nn (2≤n≤1052≤n≤105) — the number of elements in the array aa.

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1051≤ai≤105) — elements of the array aa.

Output

Print one integer — the minimum possible instability of the array if you have to remove exactly one element from the array aa.

Examples

input

Copy

4
1 3 3 7

output

Copy

2

input

Copy

2
1 100000

output

Copy

0

Note

In the first example you can remove 77 then instability of the remaining array will be 3−1=23−1=2.

In the second example you can remove either 11 or 100000100000 then instability of the remaining array will be 100000−100000=0100000−100000=0 and 1−1=01−1=0 correspondingly.

解题说明：水题，先排序，然后判断是移除最大的数还是最小的数。

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
 
 
int n, a[100005];
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	sort(a, a + n);
	cout << min(a[n - 1] - a[1], a[n - 2] - a[0]) << endl;
}