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