Вам дан массив целых чисел \(a_1, a_2, \ldots, a_n\) и целое число \(x\).
Вам нужно выбрать максимальное количество элементов массива таким образом, чтобы для любого подотрезка массива \(a_l, a_{l + 1}, \ldots, a_r\), который содержит строго больше одного элемента \((l < r)\), выполняется хотя бы одно из двух:
- Хотя бы один элемент на этом отрезке не выбран, или
- \(a_l + a_{l+1} + \ldots + a_r \geq x \cdot (r - l + 1)\).
Примечание
В первом примере один из корректных способов выбрать элементы следующий: \([\underline{1}, 2, \underline{3}, \underline{4}, \underline{5}]\). Все подотрезки удовлетворяют хотя бы одному критерию. Например, в подотрезоке \(l = 1\), \(r = 2\) элемент \(2\) не выбран, то есть выполнен первый критерий. А в подотрезке \(l = 3\), \(r = 5\) выполняется \(3 + 4 + 5 = 12 \ge 2 \cdot 3\), удовлетворяя второй критерий.
Выбрать все элементы нельзя, так как в этом случае для \(l = 1\), \(r = 2\) все элементы будут выбраны, и \(a_1 + a_2 = 3 < 2 \cdot 2\). Таким образом, максимальное количество выбранных элементов равно \(4\).
Во втором примере один из корректных способов выбрать элементы следующий: \([\underline{2}, \underline{4}, 2, \underline{4}, \underline{2}, \underline{4}, 2, \underline{4}, \underline{2}, \underline{4}]\).
В третьем примере один из корректных способов выбрать элементы следующий: \([\underline{-10}, -5, \underline{-10}]\).
В четвертом примере один из корректных способов выбрать элементы следующий: \([\underline{9}, \underline{9}, -3]\).