「Nhk R1 F」sh...bequietaya.
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

现在有一个  的排列 a，你知道这个排列具体长什么样子。

一开始这个排列 a 的每一位上的元素是不可见的。你现在要按顺序写上  这 n 个数，在其于排列 a 上对应的位置。每次写完一个数字之后，你需要回答一个问题：将 a 上已经出现的所有数字，按位置顺序拼接成一个序列 b，计算 b 所有连续子序列的  之和。

其中  意为一个范围内没有出现的最小的自然数。例如 。

由于有太多问题了，你只需要回答所有问题的答案之和即可。

输入描述:

第一行一个整数 。

第二行  个整数表示 。

输出描述:

一个整数，表示答案。
示例1

输入

复制 
5
4 0 3 1 2

输出

复制 
35

说明

令 -1 为占位元素。

- 插入 0，则 \{x_{n-1}\}=\{-1,0,-1,-1,-1\}，去掉占位元素 \{0\}；
- 插入 1，则 \{x_{n-1}\}=\{-1,0,-1,1,-1\}，去掉占位元素 \{0,1\}；
- 插入 2，则 \{x_{n-1}\}=\{-1,0,-1,1,2\}，去掉占位元素 \{0,1,2\}；
- 插入 3，则 \{x_{n-1}\}=\{-1,0,3,1,2\}，去掉占位元素 \{0,3,1,2\}；
- 插入 4，则 \{x_{n-1}\}=\{4,0,3,1,2\}，去掉占位元素 \{4,0,3,1,2\}；

各次插入的 \text{mex} 之和是：

- 1=1（\text{mex}(\{0\})）；
- 1+2+0=3（\text{mex}(\{0\})+\text{mex}(\{0,1\})+\text{mex}(\{1\})）；
- 1+2+3+0+0+0=6；
- 1+1+2+4+0+0+0+0+0+0=8；
- 0+1+1+2+5+1+1+2+4+0+0+0+0+0+0=17；

则答案为 1+3+6+8+17=35。

示例2

输入

复制 
10
9 4 2 7 5 1 6 0 3 8

输出

复制 
264
示例3

输入

复制 
20
9 4 2 7 13 17 11 14 3 8 19 15 10 5 0 12 16 1 18 6

输出

复制 
1425

备注: