Об'єднані корови фермера Джона (Платина)

З $n$ корів формується делегація. Вони розташовані в ряд, і корова $i$ має породу $b_i$.

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

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

Вхідні дані

Перша стрічка містить кількість корів $n(1\le n\le 2\cdot 10^5)$.

Друга стрічка містить $n$ цілих чисел $b_1,b_2,\dots ,b_n(1\le b_i\le n)$.

Вихідні дані

Виведіть кількість можливих делегацій.

Приклади

Кожна делегація відповідає одному з наступних триплетів лідерів:

$(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)$.