题目描述
给定一个包含 {0,...,n−1} 中每个数恰好一次的序列 {ai},求:
n∑l=1n∑r=lmex({al,...,ar})
其中,mex(S)=min{i∈N|i∉S}。注意:在本题里, 0∈N。
输入格式
从标准输入读入数据。
输入共两行。
第一行包含一个正整数 n。
第二行是 n 个以空格隔开的非负整数,保证这 n 个数是 {0,...,n−1} 的一个排列。
输出格式
输出到标准输出。
输出一个整数,表示题目中所描述式子的答案。
样例
输入
5
4 3 1 2 0
输出
14
样例
输入
10
7 2 6 5 3 9 8 4 0 1
输出
40
解释
数据范围
对于 10% 的数据保证:n≤100。
对于 30% 的数据保证:n≤300。
对于 50% 的数据保证:n≤5000。
对于所有测试数据保证:1≤n≤106,输入的 n 个数是 {0,...,n−1} 的一个排列。
提示
请注意答案的范围!