Module: GWP (Largest Increasing Subsequence)


Problem

4 /6


NVP on the segment (A, A')

Problem

We are given a number sequence a1, ..., an . Write a program that responds to queries like "find the length of the largest strictly increasing subsequence, all elements
that are on the segment from the lith to the rith element".
A subsequence of the sequence a1 , ..., an is a sequence that can be obtained by removing several ai elements (the relative order of the remaining
elements cannot be changed). So, for example, the sequence (2, 4) is a subsequence of the sequence (1, 2, 3, 4, 5) (you can delete the elements 1, 3   and 5 ),  and the sequence (5, 1) is not.< br />  
Input
The first line contains an integer n  (1 <= n <= 3000 ) is the number of elements in the sequence. The second line contains n  Numbers separated by spaces are the elements of the sequence. All elements do not exceed 109 in absolute value. The third line contains a single integer q  (1 < ;= q <= 105) - number of requests. The following q  lines describe the queries. Description of the i -th query - two numbers li and rj  (1 <= li <= ri <= n) , separated by spaces.
 
Output data
Output q numbers - answers to queries. Numbers should be output one per line in the same order as the queries are described in the input.
 
Examples
# Input Output
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!