Плюсануть
Поделиться
Класснуть
Запинить

Задачи из рубрикатора

Тег: Двоичное дерево поиска

Условие задачи  
ID 38133: Организация коров фермера Джона
Организация коров фермера Джона
Темы: Двоичное дерево поиска   

Организация коров фермера Джона (UCFJ) направляет делегацию на Международную олимпиаду по овцеводству (IOI).
N  коров участвуют в выборе делегации (1≤N≤2⋅105). Они стоят в ряд, и корова i имеет породу bi.

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

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


Входные данные: 
Первая строка содержит N.
Вторая строка содержит N целых чисел b1,b2,…,bN, каждое в интервале [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).