B"The only difference between easy and hard versions is the maximum values of n and q . You are given an array, consisting of n integers. Initially, all elements are red. You can apply the following operation to the array multiple times. During the i -th operation, you select an element of the array; then: The operations are numbered from 1 , i. xe2 x80 x89e. during the first operation some element is changed by 1 and so on. You are asked q queries of the following form: Note that the operations don't affect the array between queries, all queries are asked on the initial array a . The first line contains two integers n and q ( 1 <= n, q <= 2 cdot 10^5 ) -- the number of elements in the array and the number of queries. The second line contains n integers a_1, a_2, ... , a_n ( 1 <= a_i <= 10^9 ). The third line contains q integers k_1, k_2, ... , k_q ( 1 <= k_j <= 10^9 ). For each query, print a single integer -- the largest minimum that the array can have after you apply exactly k operations to it. "...