Sum of Subarray Values

Given an array of length \(n\), the value of any sequence (i.e. contiguous subarray) of length \(k\) is defined as

\[ val = \max_{1 \le i \le k} \{ i \times f(i,k) \} \]

where \(f(i,j)\) denotes the number of distinct integers in the interval \([i,j]\) of that sequence (with indices relative to the subarray).

You are given an array of \(n\) integers. Consider every contiguous subarray of the given array, compute its value according to the above formula, and output the sum of the values over all contiguous subarrays.

inputFormat

The first line contains an integer (n) (the number of elements in the array). The second line contains (n) space-separated integers.

outputFormat

Output a single integer which is the sum of the values for all contiguous subarrays.

sample

3
1 2 3

11