Calentamiento global


Submit solution


Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

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


Comments

There are no comments at the moment.