Module: GWP（最大递增子序列）


Problem

4 /6


段 (A, A') 上的 NVP

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