El calentamiento global es un tema importante y Leonardo lo sabe. Decidió hacer un análisis del historial de temperaturas y encontrar una subsecuencia de días (no necesariamente consecutivos) donde la temperatura fue estrictamente creciente. ¡Convencerá a los no creyentes!

Leomnardo ha encontrado datos históricos de ~n~ días consecutivos. La temperatura en el día ~i-th~ era ~t_i~. Formalmente, estamos interesados ​​en encontrar la longitud de la subsecuencia de mayor crecimiento (LIS) de ~(t_1, t_2, ..., t_n)~, es decir, el más grande ~k~ posible para la cual es posible elegir una secuencia creciente de índices ~1 \le a_1 < a_2 < ... < a_k \le n~ tal que ~t_{a1} < t_{a2} <. . . < t_{ak}~.

Leonardo quiere encontrar una subsecuencia realmente larga y es por eso que decidió hacer un poco de trampa. Él primero elija un intervalo de días no vacíos y un entero ~d~ ~(-x \le d \le x)~ y aumentará la temperatura encada uno de esos días por ~d~. Un cambio pequeño como ese probablemente no será notado por la comunidad, mientras que en al mismo tiempo debería hacer el LIS más largo. Se permite elegir ~d = 0~.

Tarea

¿Cuál es la mayor longitud posible del LIS después de un cambio?

Entrada

La primera línea de la entrada estándar contiene dos enteros separados por espacios ~n~ y ~x~ ~(1 \le n \le 200 000, 0 \le x \le 10^9)~, el número de días y el límite para el valor absoluto de ~d~.

La segunda línea contiene n enteros ~t_1, t_2,. . . , t_n~ ~(1 \le t_i \le 10^9)~ separados por espacios, la secuencia de temperaturas históricas.

Salida

Imprima un entero, la mayor longitud posible del LIS después de un solo cambio.

Ejemplo de Entrada

8 10
7 3 5 12 2 7 3 4

Ejemplo de Salida

5

Explicación del ejemplo

Leonardo puede elegir un intervalo ~[2, 3]~ y ~d = -5~, lo que significa disminuir ~t_2~ y ~t_3~ por 5. En este caso, la nueva secuencia es ~(7, -2, 0, 12, 2, 7, 3, 4)~, donde puede encontrar un LIS ~(-2, 0, 2, 3, 4)~. La longitud del LIS es ~5~.

Calificación

El conjunto de prueba se divide en las siguientes subtareas con restricciones adicionales. Cada una de las subtareas consisten en uno o más grupos de prueba separados. Cada grupo de prueba puede contener uno o más casos de prueba.

Subtarea: 1 Restricciones: ~n, x \le 10~; Puntos: ~5~

Subtarea: 2 Restricciones: ~n, x \le 50~; Puntos: ~10~

Subtarea: 3 Restricciones: ~n \le 1000~; Puntos: ~13~

Subtarea: 4 Restricciones: ~x = 0~; Puntos: ~10~

Subtarea: 5 Restricciones: ~x \le 5~, ~n \le 50 000~; Puntos: ~20~

Subtarea: 6 Restricciones: ~x = 10^9~; Puntos: ~17~

Subtarea: 7 sin restricciones adicionales; Puntos: ~25~