Объединённые коровы Farmer John (UCFJ) отправляют делегацию на International bOvine olympIad (IOI).

В отборе участвуют $N$ коров ($1 \leq N \leq 2 \cdot 10^5$). Они стоят в ряд, и корова $i$ имеет породу $b_i$.

Делегация состоит из непрерывного отрезка не менее двух коров: коров $l\ldots r$ для целых $l$ и $r$, удовлетворяющих $1\le l<r\le N$. Две крайние коровы становятся «лидерами». Чтобы избежать конфликтов внутри породы, каждый лидер должен отличаться породой от всех остальных членов делегации, включая другого лидера.

Помогите UCFJ определить, по налоговым причинам, число способов выбрать делегацию на IOI.

Входные данные

Первая строка содержит $N$.

Вторая строка содержит $N$ целых чисел $b_1,b_2,\ldots,b_N$, каждое в диапазоне $[1,N]$.

Выходные данные

Число возможных делегаций на одной строке.

Большие целые числа в этой задаче могут потребовать 64-битного типа (например, long long в C/C++).

Примеры

Входные данные 1

7
1 2 3 4 3 2 5

Выходные данные 1

13

Примечание

Каждая делегация соответствует одной из следующих пар лидеров:

$$(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).$$

Подзадачи

• Тесты 1–3 удовлетворяют $N\le 100$.
• Тесты 4–8 удовлетворяют $N\le 5000$.
• Тесты 9–20 не имеют дополнительных ограничений.

Автор задачи: Benjamin Qi