You are given an array $x_1,x_2,\dots,x_n$. Let $d(a,b)$ denote the number of distinct values in the subarray $x_a,x_{a+1},\dots,x_b$.

Your task is to calculate the sum $\sum_{a=1}^n \sum_{b=a}^n d(a,b)$, i.e., the sum of $d(a,b)$ for all subarrays.

Input

The first line has an integer $n$: the array size.

The next line has $n$ integers $x_1,x_2,\dots,x_n$: the array contents.

Output

Print one integer: the required sum.

Constraints

• $1 \le n \le 2 \cdot 10^5$
• $1 \le x_i \le 10^9$

Example

Input:

5
1 2 3 1 1

Output:

29

Explanation: In this array, $6$ subarrays have $1$ distinct value, $4$ subarrays have $2$ distinct values and $5$ subarrays have $3$ distinct values. Thus, the sum is $6\cdot1+4\cdot2+5\cdot3=29$.