Module: GWP (mayor subsecuencia creciente)


Problem

4 /6


NVP en el segmento (A, A')

Problem

Se nos da una secuencia numérica a1, ..., an . Escriba un programa que responda a consultas como "encontrar la longitud de la mayor estrictamente subsecuencia creciente, todos los elementos
que están en el segmento desde el elemento lith al rith".< /div>
Una subsecuencia de la secuencia a1 , ..., an< /sub> es una secuencia que se puede obtener eliminando varios elementos ai (el orden relativo de los
restantes Los elementos
no se pueden cambiar). Entonces, por ejemplo, la secuencia (2, 4) es una subsecuencia de la secuencia (1, 2, 3, 4, 5) (puede eliminar los elementos 1, 3   y 5),  y la secuencia ( 5, 1) no lo es.< br />  
Entrada
La primera línea contiene un número entero n  (1 <= n <= 3000 ) es el número de elementos en la secuencia. La segunda línea contiene n< /code>  Los números separados por espacios son los elementos de la secuencia. Todos los elementos no superan 109 en valor absoluto. La tercera línea contiene un solo número entero q< /code>  (1 < ;= q <= 105) - número de solicitudes. Las siguientes q  líneas describen las consultas. Descripción de la i -ésima consulta - dos números li y rj   (1 <= li <= ri <= n) , separados por espacios.
 
Datos de salida
Números q de salida: respuestas a consultas. Los números deben generarse uno por línea en el mismo orden en que se describen las consultas en la entrada.
 
Ejemplos

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

# Entrada Salida
1 6
3 3 -5 7 4 9
6
14
1 2
23
15
3 5
25		 2
1
1
2
2
2