Maximum Sum Segment

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 ≤ l ≤ r ≤ n and 1 ≤ k ≤ 1015.

Output

For each query print the result in a new line.

Sample

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

2
3
4