解题思路

问题转化

对于任意子数组，它的权值等于“需要补充多少数字才能变成一个连续区间”。 这个数量可以写成： 权值 = (子数组最大值 − 子数组最小值) − (子数组长度 − 1)。

所以总答案就是：

题目内容

小美从一个原始的连续数列(各元素互不相同，且恰好是某个区间内的所有整数)中丢失了一些数字，剩余元素按 原顺序形成了一个长度为$n$ 的数组{$a_1,a_2,...,a_n$}。

选定区间$[l,r]$后，一定可以通过插入若干元素，使得子数组中的元素恰好构成从 $min(a_l,...,a_r)$到

$max(a_l,...,a_r)$的连续整数序列。我们称这个子数组的权值为:插入的最少元素数量。