Вам дан массив целых чисел \(a_1, a_2, \ldots, a_n\). Посчитайте количество подотрезков этого массива \(1 \leq l \leq r \leq n\), таких что:
- Массив \(b = [a_l, a_{l+1}, \ldots, a_r]\) встречается в массиве \(a\) как подпоследовательность ровно один раз. Другими словами, существует ровно один способ выбрать набор индексов \(1 \leq i_1 < i_2 < \ldots < i_{r - l + 1} \leq n\), такой что \(b_j = a_{i_j}\) для всех \(1 \leq j \leq r - l + 1\).
Выходные данные
Для каждого набора входных данных выведите количество подходящих подотрезков.
Примечание
В первом наборе входных данных существует ровно один подотрезок \((1, 1)\), который нам подходит.
В втором наборе входных данных существует ровно один подотрезок \((1, 2)\), который нам подходит. Подотрезки \((1, 1)\) и \((2, 2)\) нам не подходят, так как подпоследовательность \([1]\) встречается два раза в массиве.
В третьем наборе входных данных подходят все подотрезки кроме \((1, 1)\) и \((3, 3)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1
1
2
1 1
3
1 2 1
4
2 3 2 1
5
4 5 4 5 4
10
1 7 7 2 3 4 3 2 1 100
|
1
1
4
7
4
28
|