Module: GWP (plus grande sous-séquence croissante)


Problem

4 /6


NVP sur le segment (A, A')

Problem

On nous donne une suite de nombres a1, ..., an . Écrivez un programme qui répond à des requêtes telles que "trouver la longueur de la plus grande sous-séquence strictement croissante, tous les éléments
qui sont sur le segment du lième au rième élément".< /div>
Une sous-séquence de la séquence a1 , ..., an< /sub> est une séquence qui peut être obtenue en supprimant plusieurs éléments ai (l'ordre relatif des éléments
restants Les éléments
ne peuvent pas être modifiés). Ainsi, par exemple, la séquence (2, 4) est une sous-séquence de la séquence (1, 2, 3, 4, 5) (vous pouvez supprimer les éléments 1, 3   et 5 ),  et la séquence ( 5, 1) ne l'est pas.< br />  
Entrée
La première ligne contient un entier n  (1 <= n <= 3000 ) est le nombre d'éléments dans la séquence. La deuxième ligne contient n< /code>  Les nombres séparés par des espaces sont les éléments de la séquence. Tous les éléments ne dépassent pas 109 en valeur absolue. La troisième ligne contient un seul entier q< /code>  (1 < ;= q <= 105) - nombre de requêtes. Les lignes q suivantes décrivent les requêtes. Description de la i -ème requête - deux nombres li et rj   (1 <= li <= ri <= n) , séparés par des espaces.
 
Données de sortie
Sortir des numéros q - réponses aux requêtes. Les nombres doivent être sortis un par ligne dans le même ordre que les requêtes sont décrites dans l'entrée.
 
Exemples
# Entrée Sortie
1 6
3 3 -5 7 4 9
6
14
1 2
23
15
3 5
25		 2
1
1
2
2
2

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!