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.
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.
Print one integer: the required sum.
5 1 2 3 1 1\n · · · · \n
29\n
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$ .