Задача №114080. Глобальное потепление
Глобальное потепление — это важная проблема, и Джонни знает об этом. Он решил проанализировать историю температур и найти подпоследовательной дней (не обязательно последовательных), в которой температура строго возрастает. Это убедит неверующих!
Джонни нашёл исторические данные за \(n\) последовательных дней. Температура в \(i\)-й день была \(t_i\).
Формально, нам интересно найти длину наибольшей возрастающей подпоследовательности (НВП) последовательности \((t_1, t_2, \ldots, t_n)\), то есть наибольшее такое \(k\), что возможно выбрать возрастающую последовательность индексов \(1 \leq a_1 lt a_2 \lt \ldots \lt a_k \leq n\), для которой \(t_{a_1} \lt t_{a_2} \lt \ldots \lt t_{a_k}\).
Джонни хочет найти действительно длинную подпоследовательность, а поэтому он решил сжульничать. Сначала он выберет непустой отрезок дней и целое число \(d\) (\(-x \leq d \leq x\)), а затем увеличит температуру в каждый из этих дней на \(d\). Такое небольшое изменение, вероятно, не будет обнаружено обществом, но при этом оно может сделать длину НВП больше. Разрешено выбирать \(d = 0\).
Какая максимально возможная длина НВП после такого изменения?
Первая строка содержит два целых числа \(n\) и \(x\) (\(1 \leq n \leq 2 \cdot 10 ^ 5\), \(0 \leq x \leq 10 ^ 9\)) — количество дней и ограничение на модуль числа \(d\).
Вторая строка содержит \(n\) целых чисел \(t_1, t_2, \ldots, t_n\) (\(1 \leq t_i \leq 10 ^ 9\)) — последовательность исторических температур.
Выведите одно целое число — максимально возможную длину НВП после одного изменения.
В примере из условия Джонни может выбрать отрезок \([2; 3]\) и \(d = -5\), что означает уменьшение \(t_2\) и \(t_3\) на 5. Тогда новая последовательность — это \((7, -2, 0, 12, 2, 7, 3, 4)\), в которой можно найти НВП \((-2, 0, 2, 3, 4)\) длины \(5\).
8 10 7 3 5 12 2 7 3 4
5