409234: GYM103464 A Stegosauruses

2050. Belarusian scientists managed to recreate dinosaurs from their remains, and now you can safely meet dinosaurs walking around somewhere near Mogilev.

Mogilev Zoo urgently needs two stegosauruses for a grandiose show "Spikes and Tails" in which various animals will take part. There's not much time left, and we need to tame the stegosaurus (luckily, the animals bred by scientists are perfectly trainable).

The organizers did not decide to go somewhere for the stegosauruses, because it is not easy to deliver such animals from another city. So they decided to find stegosaurus near the zoo.

They got lucky! They found $$$n$$$ beautiful stegosaurus, and $$$i$$$th of them had $$$a_i$$$ spikes. Now they had to pick any two to put on a show.

Clearly, the stegosaurses had to look good together. So zoo director Alexandrus wants to choose them so that the number of spikes they have is almost the same. Simply put, he wants to choose such stegosaurses $$$i$$$ and $$$j$$$ that $$$|a_i - a_j|$$$ is minimal.

Here $$$|k|$$$ denotes the modulus of the number $$$k$$$, that is, $$$|k| = k$$$ if $$$k \geq 0$$$, and $$$|k| = -k$$$ otherwise. So, $$$|3| = 3$$$, and $$$|-2| = 2$$$.

Help Alexandrus determine how well he can choose stegosaurus, that is, find the minimal $$$|a_i - a_j|$$$.

The first line contains one integer $$$n$$$ —the number of stegosaurses ($$$2 \le n \le 10^5$$$).

Then the second line takes $$$n$$$ integers $$$a_i$$$ — the number of spikes of $$$i$$$th stegosaurus ($$$0 \le a_i \le 10^9$$$).

Output a single non-negative integer: the minimal possible difference between the number of spikes of two stegosaurses.

In this problem there is a test score, i.e. for each test the points are given independently, and then summed up. Tests are conventionally divided into subtasks, and points are awarded for the completion of all tests of a subtask. The subtasks are given in the following table:

5
2 6 0 19 10

2

7
1 2 1 2 4 2 3

0

2
10 15

5

In the first test case, you can choose stegosauruses with numbers $$$1$$$ and $$$3$$$, then the number of spikes they have differs by $$$2$$$.

In the second test case, you can choose stegosauruses with numbers $$$2$$$ and $$$6$$$, then the number of spikes differs by $$$0$$$. You could also choose, for example, stegosauruses with numbers $$$1$$$ and $$$3$$$.

In the third test case, you could choose stegosauruses with numbers $$$1$$$ and $$$2$$$, because there are simply no others.