该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

这是问题的困难版本。在这个版本中 $n,m\leq2*10^5$。

阿兔正在组建一支最强的战队来参加程序设计天梯赛。他有 $n$ 个候选队员，每个队员都有一个能力值 $A_i$。现在有 $m$ 次组队机会，每次可以选择一个区间 $[l, r]$ 内的队员，从中选出恰好一半（向上取整）的队员组成小队。阿兔希望每次选出的小队成员的能力值总和尽可能大，你能帮助他计算出每次组队的最佳方案吗？

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \leq n, m \leq 2*10^5$)，分别表示候选队员的数量和查询的次数。

第二行包含 $n$ 个整数 $A_1, A_2, \dots, A_n$ ($0 \leq A_i < 10^9$)，表示每个队员的能力值。

接下来的 $m$ 行，每行包含两个整数 $l_i$ 和 $r_i$ ($1 \leq l_i \leq r_i \leq n$)，表示每次查询的区间。

输出格式

对于每个查询，输出一行，表示在区间 $[l_i, r_i]$ 中选择 $\lceil (r_i - l_i+1) / 2 \rceil$ 个队员所能得到的最大能力值总和。

4 4
1 2 3 4
1 4
1 3
2 3
3 3

7
5
3
3