E. Оптимальные тренировки
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Исаак начинает свою тренировку. Доступно $$$n$$$ маршрутов, $$$i$$$-й маршрут ($$$1 \le i \le n$$$) состоит из $$$a_i$$$ участков одинаковой длины.

Дано целое число $$$u$$$ ($$$1 \le u \le 10^9$$$), завершение каждого участка может увеличить способности Исаака на определенное значение:

  • Завершение $$$1$$$-го участка увеличивает способности Исаака на $$$u$$$.
  • Завершение $$$2$$$-го участка увеличивает способности Исаака на $$$u-1$$$.
  • Завершение $$$3$$$-го участка увеличивает способности Исаака на $$$u-2$$$.
  • $$$\ldots$$$
  • Завершение $$$k$$$-го участка ($$$k \ge 1$$$) увеличивает способности Исаака на $$$u+1-k$$$. (Значение $$$u+1-k$$$ может быть отрицательным, что означает, что завершение дополнительного участка уменьшает способности Исаака.)

Также дано целое число $$$l$$$. Вы можете выбрать целое число $$$r$$$, такое что $$$l \le r \le n$$$, и тогда Исаак завершит каждый участок каждого маршрута $$$l, l + 1, \dots, r$$$ (то есть, всего $$$\sum_{i=l}^r a_i = a_l + a_{l+1} + \ldots + a_r$$$ участков).

Ответьте на следующий вопрос: какое оптимальное значение $$$r$$$ вы можете выбрать, чтобы увеличение способностей Исаака было максимальным?

Если существует несколько значений $$$r$$$, которые максимизируют увеличение способностей Исаака, выведите наименьшее значение $$$r$$$.

Для увеличения сложности вам нужно ответить на вопрос для $$$q$$$ различных значений $$$l$$$ и $$$u$$$.

Входные данные

Первая строка ввода содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Далее следуют описания наборов.

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^4$$$).

Третья строка содержит одно целое число $$$q$$$ ($$$1 \le q \le 10^5$$$).

Следующие $$$q$$$ строк содержат по два целых числа $$$l$$$ и $$$u$$$ ($$$1 \le l \le n, 1 \le u \le 10^9$$$) — описания каждого запроса.

Сумма $$$n$$$ по всем наборам входных данных теста не превышает $$$2 \cdot 10^5$$$. Сумма $$$q$$$ по всем наборам входных данных теста не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого теста выведите $$$q$$$ целых чисел: $$$i$$$-е целое число содержит оптимальное значение $$$r$$$ для $$$i$$$-го запроса. Если существует несколько решений, выведите наименьшее из них.

Пример
Входные данные
5
6
3 1 4 1 5 9
3
1 8
2 7
5 9
1
10
1
1 1
9
5 10 9 6 8 3 10 7 3
5
8 56
1 12
9 3
1 27
5 45
5
7 9 2 5 2
10
1 37
2 9
3 33
4 32
4 15
2 2
4 2
2 19
3 7
2 7
10
9 1 6 7 6 3 10 7 3 10
5
10 43
3 23
9 3
6 8
5 14
Выходные данные
3 4 5 
1 
9 2 9 4 9 
5 2 5 5 5 2 4 5 4 2 
10 6 9 7 7
Примечание

Для $$$1$$$-го запроса в первом тесте:

  • Выбрав $$$r = 3$$$, Исаак завершает $$$a_1 + a_2 + a_3 = 3 + 1 + 4 = 8$$$ участков в общей сложности, поэтому его увеличение способностей составляет $$$u+(u-1)+\ldots+(u-7)=8+7+6+5+4+3+2+1 = 36$$$.
  • Выбрав $$$r = 4$$$, Исаак завершает $$$a_1 + a_2 + a_3 + a_4 = 3 + 1 + 4 + 1 = 9$$$ участков в общей сложности, поэтому его увеличение способностей составляет $$$u+(u-1)+\ldots+(u-8)=8+7+6+5+4+3+2+1+0 = 36$$$.

Оба варианта дают оптимальное увеличение способностей, однако мы хотим выбрать наименьшее значение $$$r$$$. Поэтому мы выбираем $$$r = 3$$$.

Для $$$2$$$-го запроса в первом тесте, выбрав $$$r = 4$$$, Исаак завершает $$$a_2 + a_3 + a_4 = 1 + 4 + 1 = 6$$$ участков в общей сложности, поэтому его увеличение способностей составляет $$$u+(u-1)+\ldots+(u-5)=7+6+5+4+3+2 = 27$$$. Это оптимальное увеличение способностей.

Для $$$3$$$-го запроса в первом тесте:

  • Выбрав $$$r = 5$$$, Исаак завершает $$$a_5 = 5$$$ участков в общей сложности, поэтому его увеличение способностей составляет $$$u+(u-1)+\ldots+(u-4)=9+8+7+6+5 = 35$$$.
  • Выбрав $$$r = 6$$$, Исаак завершает $$$a_5 + a_6 = 5 + 9 = 14$$$ участков в общей сложности, поэтому его увеличение способностей составляет $$$u+(u-1)+\ldots+(u-13)=9+8+7+6+5+4+3+2+1+0+(-1)+(-2)+(-3)+(-4) = 35$$$.

Оба варианта дают оптимальное увеличение способностей, однако мы хотим выбрать наименьшее значение $$$r$$$. Поэтому мы выбираем $$$r = 5$$$.

Таким образом, вывод для первого теста: $$$[3, 4, 5]$$$.