Поданий масив \(N\) цілих чисел (назвемо його \(A\)). Знайти кількість пар індексів \(1 \le i \le j \le N\) таких, що немає жодного числа, яке зустрічається рівно один раз серед чисел \(A_i, A_{i+1}, \ldots, A_{j}\).

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

В першому рядку подане число \(1 \le N \le 200000\) - кількість елементів масиву. \ В другому рядку подано \(N\) цілих чисел \(1 \le A_i \le 10^9\) - елементи масиву.

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

Вивести одне число - відповідь до задачі.

Пояснення

В першому тесті єдиною такою парою є пара \((1, 6)\).

В другому тесті такими парами є: \((1, 2)\), \((1, 4)\), \((1, 6)\), \((3, 4)\), \((3, 6)\), \((5, 6)\).

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

6
1 2 3 1 2 3

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

1

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

6
1 1 2 2 3 3

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

6