Module: GWP(최대 증가 하위 시퀀스)


Problem

4 /6


세그먼트의 NVP(A, A')

Problem

a1, ..., an . "가장 큰 엄격하게 증가하는 하위 시퀀스, 모든 요소
의 길이 찾기"와 같은 쿼리에 응답하는 프로그램을 작성하세요.
li번째부터 ri번째 요소까지의 세그먼트에 있는 ".< / 디비전>
시퀀스 a1 , ..., an<의 하위 시퀀스 /sub> 는 여러 ai 요소를 제거하여 얻을 수 있는 시퀀스입니다(나머지
요소는 변경할 수 없습니다). 따라서 예를 들어 시퀀스 (2, 4)는 시퀀스 (1, 2, 3, 4, 5)의 하위 시퀀스이며(요소 1, 3   및 5를 삭제할 수 있음)  시퀀스( 5, 1) 아닙니다.< br />  
입력
첫 번째 줄에는 정수 n이 포함됩니다.  (1 <= n <= 3000 )은 시퀀스의 요소 수입니다. 두 번째 줄에는 n<이 포함됩니다. /code>  공백으로 구분된 숫자는 시퀀스의 요소입니다. 모든 요소는 절대값이 109을 초과하지 않습니다. 세 번째 줄에는 단일 정수 q<가 포함됩니다. /code>  (1 < ;= q <= 105) - 요청 수. 다음 q 줄은 쿼리를 설명합니다. i -번째 쿼리에 대한 설명 - 두 숫자 li 및 rj   (1 <= li <= ri <= n) , 공백으로 구분.
 
출력 데이터
출력 q 숫자 - 쿼리에 대한 답변. 숫자는 입력에 쿼리가 기술된 것과 동일한 순서로 한 줄에 하나씩 출력되어야 합니다.
 
예
<헤드> <몸>

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!

# 입력 출력
1 6
3 3 -5 7 4 9
6
14
1 2
23
15
3 5
25		 2
1
1
2
2
2