E. Turtle vs. Rabbit Race: Optimal Trainings
binary search; implementation; math; ternary search
Isaac begins his training. There are \(n\) running tracks available, and the \(i\)-th track (\(1 \le i \le n\)) consists of \(a_i\) equal-length sections. Given an integer \(u\) (\(1 \le u \le 10^9\)), finishing each section can increase Isaac's ability by a certain value, described as follows: Finishing the \(1\)-st section increases Isaac's performance by \(u\). Finishing the \(2\)-nd section increases Isaac's performance by \(u-1\). Finishing the \(3\)-rd section increases Isaac's performance by \(u-2\). \(\ldots\) Finishing the \(k\)-th section (\(k \ge 1\)) increases Isaac's performance by \(u+1-k\). (The value \(u+1-k\) can be negative, which means finishing an extra section decreases Isaac's performance.) You are also given an integer \(l\). You must choose an integer \(r\) such that \(l \le r \le n\) and Isaac will finish each section of each track \(l, l + 1, \dots, r\) (that is, a total of \(\sum_{i=l}^r a_i = a_l + a_{l+1} + \ldots + 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\).
The first line of input contains a single integer \(t\) (\(1 \le t \le 10^4\)) — the number of test cases.The descriptions of the test cases follow.The first line contains a single integer \(n\) (\(1 \le n \le 10^5\)). The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^4\)).The third line contains a single integer \(q\) (\(1 \le q \le 10^5\)).The next \(q\) lines each contain two integers \(l\) and \(u\) (\(1 \le l \le n, 1 \le u \le 10^9\)) — the descriptions to each query.The sum of \(n\) over all test cases does not exceed \(2 \cdot 10^5\). The sum of \(q\) over all test cases does not exceed \(2 \cdot 10^5\).
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.
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)+\ldots+(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)+\ldots+(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)+\ldots+(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)+\ldots+(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)+\ldots+(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]\).