З \(N\) корів вибирається делегація (\(1 \leq N \leq 2 \cdot 10^5\)). Вони стоять у ряд, корова \(i\) має породу \(b_i\).

Делегація складатиметься з безперервної ділянки корів не менше трьох, тобто корови \(l\ldots r\) для цілих \(l\) і \(r\) задовольняють умовам \(1\le l<r\le N\) і \(r-l\ge 2\). Три корови у вибраному інтервалі позначаються як лідери делегації. Дві граничні корови обов'язково мають бути лідерами. Крім того, кожен лідер повинен мати породу відмінну від решти корів у делегації (лідери чи не лідери).

Визначте кількість способів, якими можна вибрати делегацію. Дві делегації розглядаються різними, якщо вони відрізняються членами чи лідерами.

Формат вхідних даних

Перший рядок містить \(N\).

Другий рядок містить \(N\) цілих чисел \(b_1,b_2,\ldots,b_N\), кожне в інтервалі \([1,N]\).

Формат вихідних даних

Кількість можливих делегацій на одному рядку.

Використовуйте 64-бітове ціле для відповіді (long long С++).

Приклад вхідних даних

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).\)

Оцінювання:

• У тестах 1-2 \(N\le 50\).
• У тестах 3-4 \(N\le 500\).
• У тестах 5-8 \(N\le 5000\).
• У тестах 9-20 не додаткових обмежень.