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

Делегация будет состоять из непрерывного участка коров не менее трёх, то есть коровы l..r для целых l и r удовлетворяющих условиям 1 ≤ l < r ≤ n и r − l ≥ 2. Три коровы в выбранном интервале помечаются как лидеры делегации. Две граничные коровы обязательно должны быть лидерами. Кроме того, каждый лидер должен иметь породу отличную от всех остальных коров в делегации (лидеры или не лидеры).

Определите количество способов которыми можно выбрать делегацию. Две делегации рассматриваются различными, если у них отличаются члены или лидеры.

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

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

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

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

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

Используйте 64-битное целое для ответа (long long в С++).

Пример

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

(1, 2, 3), (1, 2, 4), (1, 3, 4), (1, 4, 7), (2, 3, 4), (4, 5, 6), (4, 5, 7), (4, 6, 7), (5, 6, 7).