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
hacoder:
20190816 22:31:50
For this input:


rocky_12:
20190814 09:16:03
I am stuck at test case 9 tle used segment tree with fast input output 

urjajn123:
20190812 18:09:10
TLE using segment tree 

urjajn123:
20190812 18:08:36
TLE using segment tree 

rahulsinghk:
20190810 06:43:28
TLE no matter what!! 

hacoder:
20190809 13:26:22
I don't understand what Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y } means? 

selfcoder24:
20190808 11:30:16
Do not return 0 in case of base case. Return 15008. Stupid case costed 6 WA. 

leductoan:
20190808 06:15:26
AC in one go 

const_variable:
20190803 13:53:34
I'm getting TLE even after using basic segment tree function. What part can I improve on?


s_h_i_1:
20190727 09:28:23
use segment tree . 
Added by:  Nguyen Dinh Tu 
Date:  20061101 
Time limit:  1s 
Source limit:  5000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 