砝码整理
题目描述
小象有 n 个砝码，第 i个砝码的重量为 ai 克，他现在想将这些砝码按质量从小到大排序。
Wpz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库当然大家都知道砝码是不能用手拿起来的，小象准备用机器进行操作。机器可以选定 l,r，将 [l,r] 区间内的所有砝码按质量从小到大排序。花费为 [l,r] 内砝码质量的最大值减去砝码质量的最小值。
Wpz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库小象自然希望花费最少。但是小象太小了，他可算不来，于是向你求助询问最小花费。
输入格式
第一行一个正整数 n，表示砝码个数。
Wpz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库第二行共 n个正整数，表示每个砝码的质量。
输出格式
一行一个正整数，表示最小花费。
数据范围
对于 30% 的数据：n≤100；Wpz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对于60% 的数据： n≤10^3；Wpz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对于 100% 的数据：n≤2×10^5。Wpz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对于所有数据，1≤n≤2⋅10^5， 0≤ai≤10^9。Wpz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
样例数据Wpz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入:Wpz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
6Wpz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
3 2 1 6 5 Wpz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出:Wpz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
4Wpz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
说明:Wpz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
[3 2 1] 排序费用为3-1Wpz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
[6 5 4] 排序费用为6-4Wpz100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
