n коров участвуют в выборе делегации. Они стоят в ряд, и корова i имеет породу bi.

Делегация состоит из непрерывного интервала как минимум двух коров - то есть из коров l..r для целых l и r удовлетворяющих 1 ≤ l < r ≤ n. Две внешние коровы выбранного интервала называются "лидерами". Чтобы избежать конфликта между породами коров каждый лидер должен иметь породу отличающуюся от остальных коров делегации (лидеров и не лидеров).

Определите количество способов выбрать делегацию.

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

Первая строка содержит n (1 ≤ n ≤ 2 * 105).

Вторая строка содержит n целых чисел b1, b2, .., bn, каждое в интервале [1, n].

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

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

Пример

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

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