You are given an array of size $n$. Find out how many subarrays exist, such that the first and last element of the subarray is the same, with at least 2 elements in each subarray.

A subarray is a order-wise continuous subset of an array. For the array $[ 1, 2, 3, 4, 5 ]$, valid subarrays include $[ 1, 2, 3 ]$, $[ 2, 3, 4, 5 ]$, $[ 1, 2 ]$, $[ 4, 5 ]$ whereas $[ 1, 3, 5 ]$ , $[ 2, 1 ]$ etc. are not subarrays.

Repeating elements in a subarray are considering distinct at distinct positions. That is, if the subarray $[ 1, 2, 1 ]$ comes twice in an array, it is to be counted distinctly.

Input

• First line will contain $n$, the size of the array.
• The next line will contain $n$ space separated integers  $a_i$, denoting each element in the array.

Constraints

• $1 \le n \le 10^6$
• $1 \le a_i \le 10^9$

Output

Single line containing the number of possible subarrays.