Given a sequence $\{a_i\}$ containing each number from $\{0, \dots, n-1\}$ exactly once, calculate:

$$ \sum_{l=1}^n\sum_{r=l}^n mex(\{a_l, \dots, a_r\}) $$

where $mex(S) = \min\{i \in \mathbb{N} \mid i \notin S\}$. Note: In this problem, $0 \in \mathbb{N}$.

Input

The input is read from standard input.

The input consists of two lines.

The first line contains a positive integer $n$.

The second line contains $n$ space-separated non-negative integers. It is guaranteed that these $n$ numbers are a permutation of $\{0, \dots, n-1\}$.

Output

Output to standard output.

Output a single integer representing the answer to the formula described in the problem.

Examples

Input 1

5
4 3 1 2 0

Output 1

14

Input 2

10
7 2 6 5 3 9 8 4 0 1

Output 2

40

Constraints

For $10\%$ of the data, $n \le 100$.

For $30\%$ of the data, $n \le 300$.

For $50\%$ of the data, $n \le 5000$.

For all test cases, $1 \le n \le 10^6$, and the $n$ input numbers are a permutation of $\{0, \dots, n-1\}$.

Note

Please pay attention to the range of the answer!