F. Stylish Combos
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Sasha wants to join an esports team in his favorite computer game. To do this, he sent a recording of his playthrough of a level in this game, consisting of $$$n$$$ consecutive actions. Each action is uniquely determined by its integer identifier, so the recording is a sequence of integers $$$a_1, a_2, \ldots, a_n$$$.

A contiguous subarray of the recording $$$a_l, a_{l+1}, \ldots, a_r$$$ ($$$1 \le l \le r \le n$$$) is called a stylish combo if the player never repeated the same action inside it — in other words, all numbers $$$a_l, a_{l+1}, \ldots, a_r$$$ are pairwise distinct.

The team recruiters are interested only in unique stylish combos. Two stylish combos $$$a_{l_1}, a_{l_1+1}, \ldots, a_{r_1}$$$ and $$$a_{l_2}, a_{l_2+1}, \ldots, a_{r_2}$$$ are considered the same if they have the same length $$$k = r_1 - l_1 + 1 = r_2 - l_2 + 1$$$ and for every integer $$$j$$$ from $$$0$$$ to $$$k - 1$$$ the equality $$$a_{l_1 + j} = a_{l_2 + j}$$$ holds.

Given the playthrough recording, find the number of different stylish combos Sasha performed.

Input

The first line of the input contains one integer $$$n$$$ — the number of actions in the recording ($$$1 \le n \le 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ — the identifiers of the performed actions ($$$1 \le a_i \le 10^{18}$$$).

Output

Print one integer — the number of different stylish combos in the given recording.

Examples
Input
5
2 1 2 1 3
Output
7
Input
4
7 7 7 7
Output
1
Note

In the first example, there are seven different stylish combos in the recording:

  • three combos of one action: $$$[1]$$$, $$$[2]$$$, and $$$[3]$$$;
  • three combos of two actions: $$$[2, 1]$$$, $$$[1, 2]$$$, and $$$[1, 3]$$$;
  • one combo of three actions: $$$[2, 1, 3]$$$.
The subarrays $$$[2, 1, 2]$$$ and $$$[1, 2, 1]$$$ are not stylish combos, because each of them contains repeated actions.

In the second example, all actions are the same, so the only stylish combo is $$$[7]$$$.