F. Стильные комбо
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Саша хочет попасть в киберспортивную команду по своей любимой компьютерной игре. Для этого он отправил запись своего прохождения уровня в этой игре, состоящую из $$$n$$$ последовательных действий. Каждое действие однозначно определяется своим целочисленным идентификатором, поэтому запись представляет собой последовательность целых чисел $$$a_1, a_2, \ldots, a_n$$$.

Непрерывный подотрезок записи $$$a_l, a_{l+1}, \ldots, a_r$$$ ($$$1 \le l \le r \le n$$$) называется стильным комбо, если внутри него игрок ни разу не повторил одно и то же действие — иными словами, все числа $$$a_l, a_{l+1}, \ldots, a_r$$$ попарно различны.

Рекрутерам команды интересны только уникальные стильные комбо. Два стильных комбо $$$a_{l_1}, a_{l_1+1}, \ldots, a_{r_1}$$$ и $$$a_{l_2}, a_{l_2+1}, \ldots, a_{r_2}$$$ считаются одинаковыми, если они имеют равную длину $$$k = r_1 - l_1 + 1 = r_2 - l_2 + 1$$$ и для каждого целого $$$j$$$ от $$$0$$$ до $$$k - 1$$$ выполняется равенство $$$a_{l_1 + j} = a_{l_2 + j}$$$.

По данной записи прохождения найдите количество различных стильных комбо, которые выполнил Саша.

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

В первой строке входных данных находится одно целое число $$$n$$$ — количество действий в записи ($$$1 \le n \le 10^5$$$).

Во второй строке находятся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ — идентификаторы выполненных действий ($$$1 \le a_i \le 10^{18}$$$).

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

Выведите одно целое число — количество различных стильных комбо в данной записи.

Примеры
Входные данные
5
2 1 2 1 3
Выходные данные
7
Входные данные
4
7 7 7 7
Выходные данные
1
Примечание

В первом примере в записи встречаются семь различных стильных комбо:

  • три комбо из одного действия: $$$[1]$$$, $$$[2]$$$ и $$$[3]$$$;
  • три комбо из двух действий: $$$[2, 1]$$$, $$$[1, 2]$$$ и $$$[1, 3]$$$;
  • одно комбо из трех действий: $$$[2, 1, 3]$$$.
Подотрезки $$$[2, 1, 2]$$$ и $$$[1, 2, 1]$$$ не являются стильными комбо, так как в каждом из них есть повторяющиеся действия.

Во втором примере все действия одинаковы, поэтому единственным стильным комбо является $$$[7]$$$.