Calentamiento global
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 días consecutivos. La temperatura en el día era . Formalmente, estamos interesados en encontrar la longitud de la subsecuencia de mayor crecimiento (LIS) de , es decir, el más grande posible para la cual es posible elegir una secuencia creciente de índices tal que .
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 y aumentará la temperatura encada uno de esos días por . 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 .
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 y , el número de días y el límite para el valor absoluto de .
La segunda línea contiene n enteros 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 y , lo que significa disminuir y por 5. En este caso, la nueva secuencia es , donde puede encontrar un LIS . La longitud del LIS es .
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: ; Puntos:
Subtarea: 2 Restricciones: ; Puntos:
Subtarea: 3 Restricciones: ; Puntos:
Subtarea: 4 Restricciones: ; Puntos:
Subtarea: 5 Restricciones: , ; Puntos:
Subtarea: 6 Restricciones: ; Puntos:
Subtarea: 7 sin restricciones adicionales; Puntos:
Comments