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 ) はシーケンス内の要素の数です. 2 行目には n< が含まれます/code>  スペースで区切られた数字はシーケンスの要素です. すべての要素は絶対値で 109 を超えません. 3 行目には単一の整数 q< が含まれます/code>  (1 < ;= q <= 105) - リクエスト数。次の q   行はクエリを記述します。 i 番目のクエリの説明 - 2 つの数値 li と rj   (1 <= li <= ri <= n) をスペースで区切ります。
 
出力データ
出力 q 番号 - クエリへの回答。数値は、クエリが入力に記述されているのと同じ順序で、1 行に 1 つずつ出力する必要があります。
 
例
<頭> <本体>

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