Description

The United Cows of Farmer John (UCFJ) is going to select a team to participate in the International bOvine olympIad (IOI).

There are $N$ cows taking part in the team selection. They stand in a line, and cow $i$ has breed $b_i$.

The team will be a contiguous interval containing at least two cows—namely, cows $l \dots r$ for some $1 \le l < r \le N$. The cows at the two ends will be designated as leaders. To avoid conflicts within the same breed, each leader must have a breed different from every other member of the team (including the other leader).

Please help UCFJ find the number of ways to choose a team that can be sent to the IOI.

Input Format

The first line contains $N$.

The second line contains $N$ integers $b_1, b_2, \dots, b_N$, each in the range $[1, N]$.

Output Format

Output one line with the number of possible teams.

7
1 2 3 4 3 2 5

13

Hint

Sample Explanation

Each team corresponds to the following pair of leaders:

$$(1,2),(1,3),(1,4),(1,7),(2,3),(2,4),(3,4),(4,5),(4,6),(4,7),(5,6),(5,7),(6,7).$$

Constraints

$1 \le N \le 2 \times 10^5$.

Translated by ChatGPT 5