Неповний колір#13095

Неповний колір

3 секунди

256 мегабайтів

Дано масив $a$ довжини $n$ . Кожне число позначає певний колір.

Розглянемо підмасив $a_{l}, a_{l + 1}, \dots, a_{r}$ a_l,a_{l+1},\ldots,a_r. Назвемо колір неповним у цьому підмасиві, якщо підмасив містить хоча б одне входження цього кольору, але не всі його входження з початкового масиву.

Наприклад, якщо колір зустрічається в початковому масиві п'ять разів, то він буде неповним у підмасиві, який містить від одного до чотирьох його входжень.

Підмасив називається гарним, якщо в ньому рівно один неповний колір. Кожен інший колір повинен або бути повністю відсутнім у підмасиві, або входити до нього всіма своїми входженнями з початкового масиву.

Знайдіть кількість гарних підмасивів.

Вхідні дані

У першому рядку задано ціле число $n$ ( $1 \leq n \leq 2 \cdot 1 0^{5}$ 1 \leq n \leq 2 \cdot 10^5) — довжину масиву.

У другому рядку задано $n$ цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1,a_2,\ldots,a_n ( $1 \leq a_{i} \leq n$ 1 \leq a_i \leq n) — кольори елементів масиву.

Вихідні дані

Виведіть одне ціле число — кількість гарних підмасивів.

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

У першому прикладі є $8$ гарних підмасивів. Наприклад, у підмасиві $a_{1}, a_{2}, a_{3}$ a_1,a_2,a_3 колір $1$ неповний, а колір $2$ входить усіма своїми входженнями. Підмасив $a_{1}, a_{2}$ a_1,a_2 не є гарним, оскільки в ньому два неповні кольори.

У другому прикладі кожен непорожній підмасив, крім усього масиву, містить неповний колір $4$ . Таких підмасивів $9$ .

У третьому прикладі кожен колір зустрічається в початковому масиві рівно один раз, тому він не може бути неповним. Гарних підмасивів немає.

Оцінювання

$20$ балів — усі елементи масиву однакові.
$40$ балів — $n \leq 100$ n \leq 100.
$60$ балів — $n \leq 2000$ n \leq 2000.
$60$ балів — $a_{i} \leq 2$ a_i \leq 2.
$100$ балів — у масиві не більше ніж $20$ різних кольорів.
$120$ балів — без додаткових обмежень.