Единственное отличие между простой и сложной версиями — максимальные значения \(n\) и \(q\).
Задан массив, состоящий из \(n\) целых чисел. Изначально все элементы красные.
К массиву можно несколько раз применить следующую операцию. На \(i\)-й операции вы выбираете элемент массива; затем:
Операции нумеруются с \(1\), т. е. на первой операции некоторый элемент изменяется на \(1\) и так далее.
К массиву задаются \(q\) запросов следующего вида:
Обратите внимание, что операции не изменяют массив между запросами, все запросы задаются к начальному массиву \(a\).
В первой строке записано два целых числа \(n\) и \(q\) (\(1 \le n, q \le 2 \cdot 10^5\)) — количество элементов массива и количество запросов.
Во второй строке записаны \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)).
В третьей строке записаны \(q\) целых чисел \(k_1, k_2, \dots, k_q\) (\(1 \le k_j \le 10^9\)).
На каждый запрос выведите одно целое число — наибольший минимум, который может быть в массиве после того как вы примените ровно \(k\) операций к нему.
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
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
2 5 2 3 10 6 8 1 3
10 7 8 3 3
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач