问题2599--愤怒的小鸟(bird)

2599: 愤怒的小鸟(bird)

时间限制: 1 Sec  内存限制: 128 MB
提交: 38  解决: 16
[提交] [状态] [讨论版] [命题人:]

题目描述

小A最近迷上了愤怒的小鸟这一款游戏,很快就通关了,但是他还是想要玩这个游戏,而且因为学业繁忙,他每天只能玩一关,有时候因为太忙了,他甚至来不及挑选自己最喜欢的关卡来玩,只好随便点一个他已经玩过了的关卡玩,但这并不能够减轻他对于愤怒的小鸟这款游戏的喜爱。
但是有一天,他的平板中病毒了,数据被毁了大半,愤怒的小鸟的通关数据也没能够避免这一场灾祸,只留下了中间一段时间的通关记录,所以小A现在想要知道他如果想要重新通关,他要从哪一关打起(该关要是小A第一个没有通关记录的关卡)。
然而小A也不知道中间留下了哪段时间的通关记录,所以只好请你对于每种情况求出他要从哪一关打起,然后将这个值求和告诉小A。
由于有教学关的存在,所以有第0关。
(题目本质是求任意区间的mex值之和)

输入

第一行一个整数n表示之前小A玩了多少天愤怒的小鸟。
接下来一行n个整数表示每一天小A玩的是哪一关。

输出

一个整数,表示每种情况下小A需要打的关卡的编号之和。

样例输入 Copy

10
1 4 2 3 0 5 2 3 4 1

样例输出 Copy

79

提示

对于30%的数据,n≤5000。
对于另30%的数据,每天玩的关卡集合包括[0,n-1]的所有整数,即每天玩的关卡序列为一个[0,n-1]的排列。
对于100%的数据,n≤100000。

来源/分类