GSS2  Can you answer these queries II
Being a completist and a simplist, kid Yang Zhe cannot solve but get Wrong Answer from most of the OI problems. And he refuse to write two program of same kind at all. So he always failes in contests.
When having a contest, Yang Zhe looks at the score of every problems first. For the problems of the same score, Yang Zhe will do only one of them. If he's lucky enough, he can get all the scores wanted.
Amber is going to hold a contest in SPOJ. She has made a list of N candidate problems, which fit Yang Zhe very well. So Yang Zhe can solve any problem he want. Amber lined up the problems, began to select. She will select a subsequence of the list as the final problems. Being A girl of great compassion, she'd like to select such a subsequence (can be empty) that Yang Zhe will get the maximal score over all the possible subsequences.
Amber found the subsequence easily after a few minutes. To make things harder, Amber decided that, Yang Zhe can take this contest only if Yang Zhe can answer her Q questions. The question is: if the final problems are limited to be a subsequence of list[X..Y] (1 <= X <= Y <= N), what's the maximal possible score Yang Zhe can get?
As we know, Yang Zhe is a bit idiot (so why did he solve the problem with a negative score?), he got Wrong Answer again... Tell him the correct answer!
Input
 Line 1: integer N (1 <= N <= 100000);
 Line 2: N integers denoting the score of each problem, each of them is a integer in range [100000, 100000];
 Line 3: integer Q (1 <= Q <= 100000);
 Line 3+i (1 <= i <= Q): two integers X and Y denoting the ith question.
Output
 Line i: a single integer, the answer to the ith question.
Example
Input: 9 4 2 2 3 1 4 2 2 6 3 1 2 1 5 4 9 Output: 4 5 3Warning: large input/output data,be careful with certain languages
hide comments
Karol KonaszyĆ±ski:
20130125 14:51:16
The statement is horrible. Clarification:


Raghavendran Ramachandran:
20121009 04:41:21
3


Yang Zhe:
20120921 06:07:22
@Walrus, yes you are right. What Amber choose is a substring from position I to position J. She can't jump over negative score between I and J. 

1,729.000:
20120622 14:03:56
I cannot understand the author at all... can anyone explain it for me?


Dongdong.Chen:
20120530 08:19:51
Will Yang Zhe do two problems with the same score if there is another problem between them ? What is the answer of this:


Varun Nitish:
20120308 08:57:20
can somebody please explain the sample outputs? i couldn't understand how the numbers were calculated... 

Bill:
20110722 03:03:21
Since that the statement says "For the problems of the same score, Yang Zhe will do only one of them", then no matter how many problems are between two problems of the same score, only one could be counted. Then the answer to your data would be: 3. 

Nic Roets:
20110531 22:50:05
Will Yang Zhe do two problems with the same score if there is another problem between them ? What is the answer of this:


Walrus:
20110222 14:22:29
I think that the author means that amber can choose a substring and not subsequence. This is the only way the sample IO can be explained. Please tell me if i am wrong. Last edit: 20110222 14:34:16 
Added by:  Fudan University Problem Setters 
Date:  20070516 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: C99 ERL JSRHINO 
Resource:  Description, standard program and test data by Yang Zhe 