У вас есть массив \(a_1, a_2, \dots, a_n\).
Назовем подотрезок \(a_l, a_{l + 1}, \dots , a_r\) этого массива подперестановкой если он содержит все числа от \(1\) до \(r-l+1\) ровно по одному разу. Например, массив \(a = [2, 2, 1, 3, 2, 3, 1]\) содержит \(6\) подотрезков, являющихся подперестановками: \([a_2 \dots a_3]\), \([a_2 \dots a_4]\), \([a_3 \dots a_3]\), \([a_3 \dots a_5]\), \([a_5 \dots a_7]\), \([a_7 \dots a_7]\).
Вам нужно посчитать количество подперестановок.
Выходные данные
В единственной строке выведите количество подперестановок массива \(a\).
Примечание
В первом тестовом примере \(7\) подперестановок: \([1, 4]\), \([3, 3]\), \([3, 6]\), \([4, 7]\), \([6, 7]\), \([7, 7]\) и \([7, 8]\).
Во втором тестовом примере \(6\) подперестановок: \([1, 1]\), \([2, 2]\), \([2, 3]\), \([3, 4]\), \([4, 4]\) и \([4, 5]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
2 4 1 3 4 2 1 2
|
7
|
|
2
|
5
1 1 2 1 2
|
6
|