解题思路

问题转化

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

所以总答案就是：

题目内容

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

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

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

请你计算数组中所有子数组的权值之和。

输入描述

第一行输入一个整数$n(1≦n≦2×10^5)$表示数组长度。

第二行输入$n$个互不相同的整数{$a_1,a_2,...,a_n$}$(1≦a_i≦10^6)$表示数组元素.

输出描述

输出一个整数，表示数组中所有子数组的权值之和。

样例1

输入

3
3 1 2

输出

1 

说明

在第一个样例中，所有子数组及其所需插入数如下:

• $[1,1] =${$3$}, $min =3, max=3$，需插入$0$个元素

• $[1, 2]=${$3, 1$}, $min =1,max=3$需入$1$个元素;

• $[1,3]=${$3,1,2$}，需插入$0$个元素;

• $[2,2]=${$1$}，需插入$0$个元素;

• $[2,3]=${$1, 2$}，需插入$0$个元素;

• $[3,3]=$ {$2$}，需插入$0$个元素;

权值之和为$0+1+0+0+0+0=1$

样例2

输入

4
2 5 3 8

输出

14