CodeForces 1095B Array Stabilization

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

4
1 3 3 7

2

2
1 100000

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 <cmath>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

int n,a[100000+8],sum[100000+8],r = 0,number[100000+8],g = 0;
int main()
{
    scanf("%d",&n);
    for(int i = 0; i<n; i++)
    {
        scanf("%d",&a[i]);
    }
    sort(a,a+n);
    if(n == 2)printf("0n");
    else printf("%dn",min(a[n-2]-a[0],a[n-1]-a[1]));
    return 0;
}