Массив \(b\) из \(m\) целых чисел называется хорошим, если после его сортировки выполняется \(b_{\left\lfloor \frac{m + 1}{2} \right\rfloor} = b_{\left\lceil \frac{m + 1}{2} \right\rceil}\). Другими словами, \(b\) является хорошим, если обе его медианы равны. В частности, если \(m\) нечетно, то \(\left\lfloor \frac{m + 1}{2} \right\rfloor = \left\lceil \frac{m + 1}{2} \right\rceil\), поэтому \(b\) гарантированно будет хорошим, если он имеет нечетную длину.
Вам дан массив \(a\) из \(n\) целых чисел. Вычислите количество хороших подмассивов\(^{\text{∗}}\) в \(a\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество хороших подмассивов в \(a\).
Примечание
В первом наборе входных данных каждый подмассив является хорошим, поскольку все его элементы равны \(1\).
Во втором наборе входных данных примером хорошего подмассива является \(b = [10, 2, 3, 3]\). Если его отсортировать, то \(b = [2, 3, 3, 10]\), значит, \(b_{\left\lfloor \frac{4 + 1}{2} \right\rfloor} = b_{\left\lceil \frac{4 + 1}{2} \right\rceil} = b_2 = b_3 = 3\). Другим примером может быть \(b = [1, 10, 2]\). С другой стороны, \(b = [1, 10]\) не подходит, поскольку его две медианы равны \(1\) и \(10\), и они не равны.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4
1 1 1 1
5
1 10 2 3 3
10
6 3 2 3 5 3 4 2 3 5
|
10
11
42
|