Из N коров выбирается делегация (1≤N≤2⋅10
5). Они стоят в ряд, корова i имеет породу b
i.
Делегация будет состоять из непрерывного участка коров не менее трёх, то есть коровы l…r для целых l и r удовлетворяющих условиям 1≤l<r≤N и r−l≥2. Три коровы в выбранном интервале помечаются как лидеры делегации. Две граничные коровы обязательно должны быть лидерами. Кроме того, каждый лидер должен иметь породу отличную от всех остальных коров в делегации (лидеры или не лидеры).
Определите количество способов которыми можно выбрать делегацию. Две делегации рассматриваются различными, если у них отличаются члены или лидеры.
Входные данные:
Первая строка содержит N.
Вторая строка содержит N целых чисел b
1,b
2,…,b
N, каждое в интервале [1,N].
Выходные данные:
Количество возможных делегаций на одной строке.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
7
1 2 3 4 3 2 5 |
9 |
Каждая делегация соответствует одному из следующих триплетов лидеров:
(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). |