求和

mex

• 时间限制：2.0 秒
• 内存限制：512 MiB
• 输入输出：标准输入输出

题目描述

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

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

输入格式

输入共两行。

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

第二行是 $n$ 个以空格隔开的非负整数，保证这 $n$ 个数是 $\{0, \ldots, 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 \le 100$。
• 对于 30% 的数据保证：$n \le 300$。
• 对于 50% 的数据保证：$n \le 5000$。
• 对于 75% 的数据保证：$n \le 2 \times 10^5$。
• 对于所有测试数据保证：$1 \le n \le 10^6$，输入的 $n$ 个数是 $\{0, \ldots, n-1\}$ 的一个排列。

提示

请注意答案的取值范围！