QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 8634. 求和

Statistics

题目描述

给定一个包含 $\{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\}$ 的一个排列。

输出格式

输出到标准输出。

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

样例

输入

5
4 3 1 2 0

输出

14

样例

输入

10
7 2 6 5 3 9 8 4 0 1

输出

40

解释

数据范围

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

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

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

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

提示

请注意答案的范围!