Вам дана перестановка \(p_1, p_2, \ldots, p_n\) длины \(n\) чисел \(0, \ldots, n - 1\). Посчитайте количество подотрезков \(1 \leq l \leq r \leq n\) этой перестановки, таких что \(mex(p_l, p_{l+1}, \ldots, p_r) > med(p_l, p_{l+1}, \ldots, p_r)\).
\(mex\) множества чисел \(S\) — это минимальное неотрицательное целое число, которое не встречается в множестве \(S\). Например:
- \(mex({0, 1, 2, 3}) = 4\)
- \(mex({0, 4, 1, 3}) = 2\)
- \(mex({5, 4, 0, 1, 2}) = 3\)
\(med\) множества чисел \(S\) — это медиана множества, то есть элемент, который после сортировки элементов по неубыванию будет стоять на позиции номер \(\left \lfloor{ \frac{|S| + 1}{2} } \right \rfloor\) (элементы массива нумеруются начиная с \(1\) и здесь \(\left \lfloor{v} \right \rfloor\) обозначает округление вниз до наибольшего целого числа, не большего \(v\)). Например:
- \(med({0, 1, 2, 3}) = 1\)
- \(med({0, 4, 1, 3}) = 1\)
- \(med({5, 4, 0, 1, 2}) = 2\)
Последовательность из \(n\) чисел называется перестановкой, если она содержит в себе все числа от \(0\) до \(n - 1\) ровно по одному разу.
Выходные данные
Для каждого набора входных данных выведите в единственной строке ответ — количество подотрезков \(1 \leq l \leq r \leq n\) этой перестановки, таких что \(mex(p_l, p_{l+1}, \ldots, p_r) > med(p_l, p_{l+1}, \ldots, p_r)\).
Примечание
В первом наборе входных данных есть один ровно один подотрезок и на нем \(mex({0}) = 1 > med({0}) = 0\).
В третьем наборе входных данных на данных подотрезках \([1, 0]\), \([0]\), \([1, 0, 2]\) и \([0, 2]\) \(mex\) большем чем \(med\).
В четвертом наборе входных данных на данных подотрезках \([0, 2]\), \([0]\), \([0, 2, 1]\) и \([0, 2, 1, 3]\) \(mex\) большем чем \(med\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
1
0
2
1 0
3
1 0 2
4
0 2 1 3
5
3 1 0 2 4
6
2 0 4 1 3 5
8
3 7 2 6 0 1 5 4
4
2 0 1 3
|
1
2
4
4
8
8
15
6
|