题目背景

题目描述

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

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

其中，$mex(S)=min\{i\in \mathbb{N}|i\notin S\}$。注意：在本题里， $0\in \mathbb{N}$。

输入格式

输入共两行。

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

第二行是 $n$ 个以空格隔开的非负整数，保证这 $n$ 个数是 $\{0,...,n-1\}$ 的一个排列。

输出格式

输出一个整数，表示题目中所描述式子的答案。

输入样例 #1

5
4 3 1 2 0

输出样例 #1

14

输入样例 #2

10
7 2 6 5 3 9 8 4 0 1

输出样例 #2

40

说明提示

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

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

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

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

对于所有测试数据保证：$1\le n\le 10^6$，输入的 $n$ 个数是 $\{0,...,n-1\}$ 的一个排列。

请注意答案的取值范围！

本站补充：原套别：第 14 套 A 题。