G. Baklava's Baklava
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Baklava has a baklava with $$$N$$$ layers. Each layer has a flavor level, $$$f_i$$$, where $$$1 \leq f_i \leq N$$$. A "baklava interval" is defined as a contiguous sequence of layers. Two intervals are different if their start or end layer positions are different.

Baklava wants you to find the number of unique intervals in the baklava that satisfy the properties:

1. $$$f_i == f_j$$$ where $$$i$$$ and $$$j$$$ are the start and end layer positions of the interval.

2. For every layer $$$k$$$ where $$$i \lt k \lt j$$$, either $$$f_k == f_i == f_j$$$ or $$$f_k$$$ appears only once between the layers $$$[i, j]$$$.

Input

The first line of input will have an integer $$$N$$$. $$$(2 \leq N \leq 100,000)$$$

The next line of input will have $$$N$$$ integers where the $$$i^{th}$$$ integer depicts $$$f_i$$$. $$$(1 \leq f_i \leq N)$$$

Output

Please output one integer, the number of intervals that satisfy Baklava's defined properties above.

Examples
Input
5
1 2 3 1 3
Output
2
Input
10
1 3 4 5 1 5 4 2 2 2
Output
5
Input
2
1 1
Output
1