题目描述

小象有 $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$。