Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Maximum Sum Segment

By prodip_bsmrstu · Limits 1s, 512 MB

You are given an array a of n positive integers. You Have to perform Q query on it.
In each query, you will be given three positive integers l, r, k.
In response to the query you have to tell the maximum number of elements you can choose from the segment [l, r] such that their sum is not more than k.

Input

The first will contain a positive integer n (1 ≤ n ≤ 105) the number of elements in the array a.
The next line contains n positive integers a1, a2, a3 … an where ai (1 ≤ ai ≤ 109) is the value of the ith element in a.
The next line will contain an integer q (1 ≤ q ≤ 105), the number of query.
In each query you will be given three positive integers l, r, k where 1 ≤ lr ≤ n and 1 ≤ k ≤ 1015.

Output

For each query print the result in a new line.

Sample

InputOutput
5
1 2 3 4 5
3
1 3 5
2 4 10
1 5 14
2
3
4

Discussion

Statistics


13% Solution Ratio

RamprosadGEarliest, 1M ago

Gazi_MohaiminFastest, 0.2s

RamprosadGLightest, 40 MB

likhon5Shortest, 2438B

Submit

Login to submit