QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100
[0]

# 8634. 求和

Statistics

题目描述

给定一个包含 {0,...,n1} 中每个数恰好一次的序列 {ai},求:

nl=1nr=lmex({al,...,ar})

其中,mex(S)=min{iN|iS}。注意:在本题里, 0N

输入格式

从标准输入读入数据。

输入共两行。

第一行包含一个正整数 n

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

输出格式

输出到标准输出。

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

样例

输入

5
4 3 1 2 0

输出

14

样例

输入

10
7 2 6 5 3 9 8 4 0 1

输出

40

解释

数据范围

对于 10% 的数据保证:n100

对于 30% 的数据保证:n300

对于 50% 的数据保证:n5000

对于所有测试数据保证:1n106,输入的 n 个数是 {0,...,n1} 的一个排列。

提示

请注意答案的范围!