Единственное отличие между простой и сложной версиями — максимальные значения \(n\) и \(q\).
Задан массив, состоящий из \(n\) целых чисел. Изначально все элементы красные.
К массиву можно несколько раз применить следующую операцию. На \(i\)-й операции вы выбираете элемент массива; затем:
- если элемент красный, то он увеличивается на \(i\) и становится синим;
- если элемент синий, то он уменьшается на \(i\) и становится красным.
Операции нумеруются с \(1\), т. е. на первой операции некоторый элемент изменяется на \(1\) и так далее.
К массиву задаются \(q\) запросов следующего вида:
- дано целое число \(k\), какой может быть наибольший минимум в массиве после того как вы примените ровно \(k\) операций к нему?
Обратите внимание, что операции не изменяют массив между запросами, все запросы задаются к начальному массиву \(a\).
Выходные данные
На каждый запрос выведите одно целое число — наибольший минимум, который может быть в массиве после того как вы примените ровно \(k\) операций к нему.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 10
5 2 8 4
1 2 3 4 5 6 7 8 9 10
|
3 4 5 6 7 8 8 10 8 12
|
|
2
|
5 10
5 2 8 4 4
1 2 3 4 5 6 7 8 9 10
|
3 4 5 6 7 8 9 8 11 8
|
|
3
|
2 5
2 3
10 6 8 1 3
|
10 7 8 3 3
|