1095B Array Stabilization

喜欢ヅ旅行 2022-04-10 07:11 71阅读 0赞

题意：给了n个数字，删除一个数，然后让最大的数减最小的数最小。

题解：排序后， 有两种删除方法，要么删除第一个要么删除最后一个，所以两个中取最小。

B. Array Stabilization

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

input

Copy

2
    1 100000

output

Copy

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.

c++：

#include<bits/stdc++.h>
    using namespace std;
    int n,a[100010];
    int main()
    {
        cin>>n;
        for(int i=0;i<n;i++)
            cin>>a[i];
        sort(a,a+n);
        if(n==2)cout<<0<<endl;
        else cout<<min(a[n-2]-a[0],a[n-1]-a[1])<<endl;
        return 0;
    }

python：

n=int(input())
    a=sorted(map(int,input().split()))
    print(min(a[-2]-a[0],a[-1]-a[1]))