Об'єднані корови фермера Джона (UCFJ) відправляють делегацію на Міжнародну олімпіаду з інформатики (IOI).

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

Делегація складатиметься з інтервалу принаймні з двох корів - тобто корів ~l\ldots r~ для цілих чисел ~l~ і ~r~, які задовольняють ~1\le l<r\le N~. Дві бічні корови вибраного інтервалу будуть визначені як "лідери". Щоб уникнути конфлікту між породами, кожен лідер повинен бути іншої породи від решти делегації (лідерів або ні).</p>

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

Input

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

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

Output

Виведіть одне ціле число.

Оцінювання

• Для ~15~ балів ~N \le 100~.
• Для ~40~ балів ~N \le 5000~.

Sample Input 1

7
1 2 3 4 3 2 5

Sample Output 1

13

Notes

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

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