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

题目描述

小象有 $n$ 个砝码，第 $i$ 个砝码的重量为 $a_i$ 克，他现在想将这些砝码按质量从小到大排序。

当然大家都知道砝码是不能用手拿起来的，小象准备用机器进行操作。机器可以选定 $l,r$，将 $[l,r]$ 区间内的所有砝码按质量从小到大排序。花费为 $[l,r]$ 内砝码质量的最大值减去砝码质量的最小值。

小象自然希望花费最少。但是小象太小了，他可算不来，于是向你求助询问最小花费。

输入格式

第一行一个正整数 $n$，表示砝码个数。

第二行共 $n$ 个正整数，表示每个砝码的质量。

输出格式

一行一个正整数，表示最小花费。

6
3 2 1 6 5 4

4

样例解释 1

[3 2 1] 排序费用为 3-1
[6 5 4] 排序费用为 6-4

数据规模与约定

• 对于 $30\%$ 的数据：$n \leq 100$；
• 对于 $60\%$ 的数据：$n \leq 10^3$；
• 对于 $100\%$ 的数据：$n \leq 2 \times 10^5$。
• 对于所有数据，$1 \le n \le 2 \cdot 10^5$，$0 \le a_i \le 10^9$。