Intervals of Unique Numbers

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

Medium5Two pointersSliding windowHash mapArrayInterviewNo attempts yetTime limit1sMemory limit32 MB

Description

Examples3

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.