简单版和困难版之间的唯一区别是 $$$n$$$ 和 $$$q$$$ 的最大值。
给定一个数组,由 $$$n$$$ 整数组成。最初,所有元素都是红色的。
您可以多次对数组应用以下操作。在第 $$$i$$$ 操作期间,您选择了数组的一个元素;那么:
- 如果元素是红色的,它会增加 $$$i$$$ 并变成蓝色;
- 如果元素是蓝色的,它会减少 $$$i$$$ 并变成红色。
操作从 $$$1$$$ 开始编号,i。 e.在第一次操作期间,某些元素被 $$$1$$$ 更改,依此类推。
系统会向您询问以下形式的 $$$q$$$ 查询:
- 给定一个整数 $$$k$$$,如果对其应用精确的 $$$k$$$ 运算,数组中最大的最小值是多少?
请注意,这些操作不会影响查询之间的数组,所有查询都针对初始数组 $$$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$$$ 操作后数组可以拥有的最大最小值。
示例
输入 #1
4 10 5 2 8 4 1 2 3 4 5 6 7 8 9 10
输出 #1
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
输出 #2
3 4 5 6 7 8 9 8 11 8
输入 #3
2 5 2 3 10 6 8 1 3
输出 #3
10 7 8 3 3