Исаак начинает свою тренировку. Доступно \(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\).
Выходные данные
Для каждого теста выведите \(q\) целых чисел: \(i\)-е целое число содержит оптимальное значение \(r\) для \(i\)-го запроса. Если существует несколько решений, выведите наименьшее из них.
Примечание
Для \(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]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|