You are given a sequence A[1], A[2], ..., A[N] . ( |A[i]| ≤ 15007 , 1 ≤ N ≤ 200000 ). 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.


给定长度为 n 的序列 a1,a2,⋯,an。现在有 m 次询问操作，每次给定 li,ri，查询 [l_i,r_i] 区间内的最大子权和。
区间 [l,r] 的最大子权和被定义为 max{a_i+a_i+1+⋯+a_j−1+a_j∣l≤i≤j≤r}。
∣a_i∣≤15007，1≤n≤2×10⁵。

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.

Your program should output the results of the M queries, one query per line.

数据结构 线段树 树状数组