GSS1  Can you answer these queries I
You are given a sequence A[1], A[2], ..., A[N] . ( A[i] ≤ 15007 , 1 ≤ N ≤ 50000 ). A query is defined as follows:
Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y }.
Given M queries, your program must output the results of these queries.
Input
 The first line of the input file contains the integer N.
 In the second line, N numbers follow.
 The third line contains the integer M.
 M lines follow, where line i contains 2 numbers xi and yi.
Output
Your program should output the results of the M queries, one query per line.
Example
Input: 3 1 2 3 1 1 2 Output: 2
hide comments
Abhishek Kainth:
20161231 19:27:01
Got several WAs because of using int :/ 

yashar shahi:
20161231 16:36:08
don't forget to use fast IO!!


siddharth_0196:
20161227 16:04:20
When 1 typo leads to a series of WAs and TLEs. :/


Rezaul H Sagar:
20161225 20:30:16
What does Max { a[i]+a[i+1]+...+a[j]} mean? Range Maximum Query or Range Sum Query? 

Abhishek Jaisingh:
20161214 23:58:51
simple Segment Tree gives AC :) 

Wumbolo:
20161203 16:02:58
100th :Do GSS3 after this. 

jawad_cs:
20161118 08:42:40
taking size of array as 50000


ryuga777:
20161115 09:25:35
getting wrong answer on test case 9 .... tried almost everything... any help on corner case ?? 

kapoor_adhish:
20161016 07:39:03
getting WA ....not TLE


i_dipu:
20161007 12:35:30
used kadane algo for worst case scenario complexity is O(n*M), but TLE is the verdict !

Added by:  Nguyen Dinh Tu 
Date:  20061101 
Time limit:  0.115s0.230s 
Source limit:  5000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 