Background

Special for beginners, ^_^

Description

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

$$\sum\limits_{l=1}^n \sum\limits_{r=l}^n mex\left(\{a_l,...a_r\}\right) $$

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

Format

Input

输入共两行。

第一行包含一个正整数$n (\le10^6)$。

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

Output

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

Samples

5
4 3 1 2 0

14

10
7 2 6 5 3 9 8 4 0 1

40

Limitation

1s, 1024KiB for each test case.