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

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

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

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

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

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

样例说明：

[3 2 1] 排序费用为3-1

[6 5 4] 排序费用为6-4

数据范围

对于30\%的数据，n\leq 100

对于60\%的数据，n\leq 1000

对于100\%的数据，n\leq 2 \times10^5,a_i \leq 10^9