Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Array Stabilization

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given an array $$$a$$$ consisting of $$$n$$$ integer numbers.

Let instability of the array be the following value: $$$\max\limits_{i = 1}^{n} a_i - \min\limits_{i = 1}^{n} a_i$$$.

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

Input

The first line of the input contains one integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of elements in the array $$$a$$$.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^5$$$) — elements of the array $$$a$$$.

Output

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

Examples

Input

4 1 3 3 7

Output

2

Input

2 1 100000

Output

0

Note

In the first example you can remove $$$7$$$ then instability of the remaining array will be $$$3 - 1 = 2$$$.

In the second example you can remove either $$$1$$$ or $$$100000$$$ then instability of the remaining array will be $$$100000 - 100000 = 0$$$ and $$$1 - 1 = 0$$$ correspondingly.

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/26/2019 08:05:31 (e3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|