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

Submit

Login to submit.

Statistics

29% Solution Ratio
RamprosadGEarliest, May '20
nusuBotFastest, 0.1s
sansaquaLightest, 9.0 MB
likhon5Shortest, 2438B
Toph uses cookies. By continuing you agree to our Cookie Policy.