该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem 8D. 分组

时间限制：1s​

空间限制：256MB​

题目描述

你面前有 \(n\) 名运动员。运动员的编号从左到右依次为 \(1\) 至 \(n\) 。你知道每个运动员的力量--编号为 \(i\) 的运动员力量为 \(s_i\) 。

你想把所有运动员分成两队。每个队必须至少有一名运动员，而且每个运动员必须正好在一个队中。

你希望第一队中最强的运动员与第二队中最弱的运动员的实力相差越小越好。从形式上看，我们希望将运动员分成 \(A\) 和 \(B\) 两队，这样 \(|\max(A) - \min(B)|\) 的值就越小越好，其中 \(\max(A)\) 是 \(A\) 队运动员的最大实力， \(\min(B)\) 是 \(B\) 队运动员的最小实力。

例如，如果 \(n=5\) 和运动员的实力是 \(s=[3, 1, 2, 6, 4]\) ，那么其中一个可能的分队情况是：

• 第一队： \(A = [1, 2, 4]\) ,
• 第二队： \(B = [3, 6]\) .

在这种情况下， \(|\max(A) - \min(B)|\) 的值将等于 \(|4-3|=1\) 。本例说明了最佳分成两队的方法之一。

输出最小值 \(|\max(A) - \min(B)|\) 。

数据格式

输入

第一行，一个正整数\(n\). \(2 \le n \le 10^5\).

第二行，\(n\)个正整数\(s_i\).

输出

一个非负整数\(|\max(A) - \min(B)|\)的最小值。

样例

输入

6
2 1 3 2 4 3

输出

0