У вас есть массив a1,a2,…,an.
Назовем подотрезок al,al+1,…,ar этого массива подперестановкой если он содержит все числа от 1 до r−l+1 ровно по одному разу. Например, массив a=[2,2,1,3,2,3,1] содержит 6 подотрезков, являющихся подперестановками: [a2…a3], [a2…a4], [a3…a3], [a3…a5], [a5…a7], [a7…a7].
Вам нужно посчитать количество подперестановок.
Первая строка содержит число n (1≤n≤3⋅105).
Вторая строка содержит n чисел a1,a2,…,an (1≤ai≤n).
Этот массив может содержать одинаковые числа.
В единственной строке выведите количество подперестановок массива a.
8 2 4 1 3 4 2 1 2
7
5 1 1 2 1 2
6
В первом тестовом примере 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].
Название |
---|