The Yule Ball is approaching and the giant ballroom must be decorated. Professor Flitwick has entrusted Harry with the decoration of the giant ballroom. The ballroom will be decorated with N drapes (numbered from 1 to N). The height of the ith drape is A[i]. The drapes are sorted in non-increasing order of height (A[i]>=A[i+1] for all i where 1 i N). There are N colours (numbered from 1 to N) available for decoration. Each drape must be coloured using one of these N colours. The cost of colouring drape i with colour c is A[i]*c.

Decorating the ballroom is a big responsibility and so Professor Flitwick has decided to first test Harry to ensure that he is up to the task. Professor Flitwick will ask Harry Q queries, each of which Harry must answer correctly. Each query consists of 3 integers : l, r and k. This means that only the drapes numbered from l to r (inclusive) must be coloured such that the total cost of the colouring is atmost k. Harry's objective is to make the colouring as colourful as possible. The colourfulness of a colouring is defined as the number of distinct colours which appear atleast once in the colouring. The objective is to return the maximum possible colourfulness under the cost constraint.

Formally, if C is a colouring of the drapes from l to r (inclusive) and c is a colour, f(c,C)=1 if there is atleast one drape which is coloured with colour c under the colouring C. Otherwise f(c,C)=0. colourfulness(C) is defined as the sum of f(1,C)+f(2,C)+....+f(N,C). cost(C) is the sum of the costs of colouring the drapes from l to r (inclusive) (The cost of colouring a single drape is defined above). The correct answer to the query is the maximum value of colourfulness(C) over all colourings C which satisfy cost(C)k. If there is no valid colouring which satisfies cost(C)k, then the correct answer to the query is "-1" (quotes for clarity).

Input

The first line of input contains a single integer N.
The second line contains N integers, A[1], A[2] .. A[N]. These will be sorted in non-increasing order.
The third line countains a single integer Q.
Q lines follow. Each of these lines consists of 3 space-seperated integers : l,r,k.

Output

Correctly formatted output consists of Q lines. The ith line contains a single integer : the answer to the ith query.
Note : If the cost constraint does not permit any colouring, the answer is -1.

Constraints

1N

1A[i]

1Q

1lrN

0k

Example

Input:

6 12 8 6 3 2 1 3 1 4 28 1 4 40 1 4 200

Output:

-1 2 4

Explanation

1.The minimum cost of colouring the drapes numbered from 1 to 4 is 12+8+6+3=29. So the answer to the first query is -1.

2.One way to use 2 distinct colours to colour the drapes from 1 to 4 is to colour drape 3 with colour 2 and the rest with colour 1. The cost of this equals 12+8+6*2+3=35.

3.Since the cost constraint is large, we can afford to keep all 4 colours distinct.