Isaac begins his training. There are n running tracks available, and the i-th track (1 ≤ i ≤ n) consists of a_i equal-length sections.
Given an integer u (1 ≤ u ≤ 10^9), finishing each section can increase Isaac's ability by a certain value, described as follows:
You are also given an integer l. You must choose an integer r such that l ≤ r ≤ n and Isaac will finish each section of each track l, l + 1, …, r (that is, a total of Σ_i=l^r a_i = a_l + a_l+1 + … + a_r sections).
Answer the following question: what is the optimal r you can choose that the increase in Isaac's performance is maximum possible?
If there are multiple r that maximize the increase in Isaac's performance, output the smallest r.
To increase the difficulty, you need to answer the question for q different values of l and u.
Input
The first line of input contains a single integer t (1 ≤ t ≤ 10^4) — the number of test cases.The descriptions of the test cases follow.The first line contains a single integer n (1 ≤ n ≤ 10^5). The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^4).The third line contains a single integer q (1 ≤ q ≤ 10^5).The next q lines each contain two integers l and u (1 ≤ l ≤ n, 1 ≤ u ≤ 10^9) — the descriptions to each query.The sum of n over all test cases does not exceed 2 · 10^5. The sum of q over all test cases does not exceed 2 · 10^5.
Output
For each test case, output q integers: the i-th integer contains the optimal r for the i-th query. If there are multiple solutions, output the smallest one.
Examples
Note
For the 1-st query in the first test case: By choosing r = 3, Isaac finishes a_1 + a_2 + a_3 = 3 + 1 + 4 = 8 sections in total, hence his increase in performance is u+(u-1)+…+(u-7)=8+7+6+5+4+3+2+1 = 36. By choosing r = 4, Isaac finishes a_1 + a_2 + a_3 + a_4 = 3 + 1 + 4 + 1 = 9 sections in total, hence his increase in performance is u+(u-1)+…+(u-8)=8+7+6+5+4+3+2+1+0 = 36. Both choices yield the optimal increase in performance, however we want to choose the smallest r. So we choose r = 3.For the 2-nd query in the first test case, by choosing r = 4, Isaac finishes a_2 + a_3 + a_4 = 1 + 4 + 1 = 6 sections in total, hence his increase in performance is u+(u-1)+…+(u-5)=7+6+5+4+3+2 = 27. This is the optimal increase in performance.For the 3-rd query in the first test case: By choosing r = 5, Isaac finishes a_5 = 5 sections in total, hence his increase in performance is u+(u-1)+…+(u-4)=9+8+7+6+5 = 35. By choosing r = 6, Isaac finishes a_5 + a_6 = 5 + 9 = 14 sections in total, hence his increase in performance is u+(u-1)+…+(u-13)=9+8+7+6+5+4+3+2+1+0+(-1)+(-2)+(-3)+(-4) = 35. Both choices yield the optimal increase in performance, however we want to choose the smallest r. So we choose r = 5.Hence the output for the first test case is [3, 4, 5].