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

Input 4 1 3 3 7 Output 2 Input 2 1 100000 Output 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("0\n"); else printf("%d\n", min(a[n-2]-a[0], a[n-1]-a[1])); return 0; }

 

转载于:https://www.cnblogs.com/RootVount/p/10345302.html