题目描述

给定一个包含 $\{0,…,n−1\}$ 中每个数恰好一次的序列 $\{a_i\}$ ，求：

$$\sum_{l = 1}^{n} \sum_{r = l}^{n} mex(\{a_l,...,a_r\}) $$

其中，$mex(S)=min\{k∈N|k∉S\}$，这里 $N$ 表示非负整数集。在本题 $0∈N$。

输入格式

输入两行。

第一行包含一个正整数 $n$ 。

第二行包含一个长度为 $n$ 的由不同的非负整数 $\{0,…,n−1\}$ 组成的排列序列。

输出格式

输出一行。

一行输出所求的结果。

样例 #1

样例输入 #1

5
4 3 1 2 0

样例输出 #1

14

样例 #2

样例输入 #2

10
7 2 6 3 9 8 0 4 1 5

样例输出 #2

61

提示

【样例解释】：

无

【数据范围】：

对于 $10\%$ 的数据保证：$n ≤ 100$。

对于 $30\%$ 的数据保证：$n ≤ 300$。

对于 $50\%$ 的数据保证：$n ≤ 5000$。

对于 $75\%$ 的数据保证：$n ≤ 2×10^5$。

对于 $100\%$ 的数据保证：$1 ≤ n ≤ 10^6$。输入为 $\{0,…,n−1\}$的一个排列。