Intervals of Unique Numbers

Interview

Time limit1sMemory limit32 MB

Summary

Count pairs (i, j) where the subarray from i to j has all distinct values, with N up to 100000.

Level: Medium5 of 10
Topics: Two pointers, Sliding window, Hash map, Array
Solved: No attempts yet

Problem

You are given a sequence of length $N$ . Write a program that counts the contiguous intervals in which no value appears twice.

An interval has length at least 1, and two intervals are different when their start or their end differs. In other words, count the pairs $(i, j)$ with $1 \le i \le j \le N$ such that the values from position $i$ to position $j$ are pairwise different.

Input

The first line contains the length $N$ of the sequence. ( $1 \le N \le 100000$ )

The second line contains the $N$ integers of the sequence, separated by spaces. Every value is between $1$ and $100000$ .

Output

Print the number of intervals that satisfy the condition on the first line.

Examples3

Example 1
Input
```
5
1 2 3 4 5
```
Expected output
```
15
```
Example 2
Input
```
5
1 2 3 1 2
```
Expected output
```
12
```
Example 3
Input
```
5
1 1 1 1 1
```
Expected output
```
5
```