The only difference between easy and hard versions is a number of elements in the array.

You are given an array aa consisting of nn integers. The value of the ii-th element of the array is aiai.

You are also given a set of mm segments. The jj-th segment is [lj;rj][lj;rj], where 1≤lj≤rj≤n1≤lj≤rj≤n.

You can choose some subset of the given set of segments and decrease values on each of the chosen segments by one (independently). For example, if the initial array a=[0,0,0,0,0]a=[0,0,0,0,0] and the given segments are [1;3][1;3] and [2;4][2;4] then you can choose both of them and the array will become b=[−1,−2,−2,−1,0]b=[−1,−2,−2,−1,0].

You have to choose some subset of the given segments (each segment can be chosen at most once) in such a way that if you apply this subset of segments to the array aa and obtain the array bb then the value maxi=1nbi−mini=1nbimaxi=1nbi−mini=1nbiwill be maximum possible.

Note that you can choose the empty set.

If there are multiple answers, you can print any.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.

The first line of the input contains two integers nn and mm (1≤n≤105,0≤m≤3001≤n≤105,0≤m≤300) — the length of the array aaand the number of segments, respectively.

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (−106≤ai≤106−106≤ai≤106), where aiai is the value of the ii-th element of the array aa.

The next mm lines are contain two integers each. The jj-th of them contains two integers ljlj and rjrj (1≤lj≤rj≤n1≤lj≤rj≤n), where ljlj and rjrj are the ends of the jj-th segment.

In the first line of the output print one integer dd — the maximum possible value maxi=1nbi−mini=1nbimaxi=1nbi−mini=1nbi if bb is the array obtained by applying some subset of the given segments to the array aa.

In the second line of the output print one integer qq (0≤q≤m0≤q≤m) — the number of segments you apply.

In the third line print qq distinct integers c1,c2,…,cqc1,c2,…,cq in any order (1≤ck≤m1≤ck≤m) — indices of segments you apply to the array aa in such a way that the value maxi=1nbi−mini=1nbimaxi=1nbi−mini=1nbi of the obtained array bb is maximum possible.

If there are multiple answers, you can print any.

In the first example the obtained array bb will be [0,−4,1,1,2][0,−4,1,1,2] so the answer is 66.

In the second example the obtained array bb will be [2,−3,1,−1,4][2,−3,1,−1,4] so the answer is 77.

In the third example you cannot do anything so the answer is 00.

 #include<cstdio>

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<vector>

 #include<queue>

 #include<cmath>

 #include<set>

 #define INF 0x3f3f3f3f

 #define LL long long

 using namespace std;

 const LL MOD = 1e9+;

 const int MAXN = 1e5+;

 const int MAXM = ;

 vector<int>Le[MAXN];

 vector<int>Ri[MAXN];

 int num[MAXN];

 int ans_q[MAXM];

 int N, M;

 struct data

 {

     int l, r;

 }q[MAXM];

 void update(int L, int R, int v)

 {

     for(int i = L; i <= R; i++){

         num[i]+=v;

     }

 }

 int main()

 {

     int index;

     int maxx = -INF, minn = INF;

     scanf("%d %d", &N, &M);

     for(int i = ; i <= N; i++){

         scanf("%d", &num[i]);

         maxx = max(maxx, num[i]);

         if(minn > num[i]){minn = num[i]; index = i;}

     }

     for(int i = ; i <= M; i++){

         scanf("%d %d", &q[i].l, &q[i].r);

         Le[q[i].l].push_back(i);

         Ri[q[i].r+].push_back(i);

     }

     int ans = maxx-minn;

     int tp;

     for(int i = ; i <= N; i++){

         for(int ed = ; ed < Ri[i].size(); ed++){

             tp = Ri[i][ed];

             update(q[tp].l, q[tp].r, );

         }

         for(int st = ; st < Le[i].size(); st++){

             tp = Le[i][st];

             update(q[tp].l, q[tp].r, -);

         }

         if(!Le[i].empty() || !Ri[i].empty()){

             maxx = -INF;minn = INF;

             for(int i = ; i <= N; i++){

                 maxx = max(maxx, num[i]);

                 minn = min(minn, num[i]);

             }

             if(ans < maxx-minn){

                 ans = maxx-minn;

                 index = i;

             }

         }

     }

     if(ans <= -INF){

         puts("");

         puts("");

     }

     else{

         printf("%d\n", ans);

         int cnt = ;

         for(int i = ; i <= M; i++){

             if(q[i].l <= index && q[i].r >= index){

                 ans_q[++cnt] = i;

             }

         }

         printf("%d\n", cnt);

         for(int i = ; i <= cnt; i++){

             printf("%d ", ans_q[i]);

         }

         puts("");

     }

     return ;

 }

 ////可持久化线段树优化的区间更新

 #include <bits/stdc++.h>

 #define INF 0x3f3f3f3f

 #define LL long long

 using namespace std;

 const int MAXN = 1e5+;

 const int MAXM = ;

 int N, M;

 int a[MAXN], L[MAXM], R[MAXM], ans[MAXN];

 vector<int>add[MAXN], sub[MAXN];

 struct node

 {

     int l, r;

     int maxx, minn, lazy;

 }tree[MAXN<<];

 void push_up(int k)

 {

     tree[k].maxx = max(tree[k<<].maxx, tree[k<<|].maxx);

     tree[k].minn = min(tree[k<<].minn, tree[k<<|].minn);

 }

 void push_down(int k)

 {

     if(tree[k].l != tree[k].r){

         tree[k<<].maxx += tree[k].lazy; tree[k<<].minn += tree[k].lazy;

         tree[k<<|].maxx+=tree[k].lazy; tree[k<<|].minn+=tree[k].lazy;

         tree[k<<].lazy += tree[k].lazy;

         tree[k<<|].lazy += tree[k].lazy;

     }

     tree[k].lazy = ;

 }

 void build(int k, int l, int r)

 {

     tree[k].l = l;

     tree[k].r = r;

     if(l == r){

         tree[k].maxx = a[l];

         tree[k].minn = a[l];

         tree[k].lazy = ;

         return;

     }

     int mid = (l+r)>>;

     build(k<<, l, mid);

     build(k<<|, mid+, r);

     push_up(k);

 }

 void update(int k, int l, int r, int x)

 {

     if(tree[k].lazy) push_down(k);

     tree[k].maxx+=x;

     tree[k].minn+=x;

     if(tree[k].l == l && tree[k].r == r){

         tree[k].lazy += x;

         return;

     }

     int mid = (tree[k].l + tree[k].r)>>;

     if(r <= mid){

         update(k<<, l, r, x);

     }

     else if(l > mid){

         update(k<<|, l, r, x);

     }

     else{

         update(k<<, l, mid, x);

         update(k<<|, mid+, r, x);

     }

     push_up(k);

 }

 int query_max(int k, int l, int r)

 {

     int maxx;

     if(tree[k].lazy) push_down(k);

     if(tree[k].l == l && tree[k].r == r) return tree[k].maxx;

     int mid = (tree[k].l + tree[k].r)>>;

     if(r <= mid) maxx = query_max(k<<, l, r);

     else if(l > mid) maxx = query_max(k<<|, l, r);

     else{

         maxx = max(query_max(k<<, l, mid), query_max(k<<|, mid+, r));

     }

     return maxx;

 }

 int query_min(int k, int l, int r)

 {

     int minn;

     if(tree[k].lazy) push_down(k);

     if(tree[k].l == l && tree[k].r == r) return tree[k].minn;

     int mid = (tree[k].l + tree[k].r)>>;

     if(r <= mid) minn = query_min(k<<, l, r);

     else if(l > mid) minn = query_min(k<<|, l, r);

     else

         minn = min(query_min(k<<, l, mid), query_min(k<<|, mid+, r));

     return minn;

 }

 int main()

 {

     scanf("%d %d", &N, &M);

     for(int i = ; i <= N; i++) scanf("%d", &a[i]);

     for(int i = ; i <= M; i++){

         scanf("%d%d", &L[i], &R[i]);

         sub[ L[i] ].push_back(i);

         add[ R[i] ].push_back(i);

     }

     build(, , N);

     int d = -, p;

     for(int i = ; i <= N; i++){

         for(int j = ; j < add[i-].size(); j++){

             int id = add[i-][j];

             update(, L[id], R[id], );

         }

         for(int j = ; j < sub[i].size(); j++){

             int id = sub[i][j];

             update(, L[id], R[id], -);

         }

         int det = query_max(, , N) - query_min(, , N);

         //printf("det:%d\n", det);

         if(det > d){

             d = det;

             p = i;

         }

     }

     printf("%d\n", d);

     int t = ;

     for(int i = ; i <= M; i++){

         if(L[i] <= p && p <= R[i])

             ans[t++] = i;

     }

     printf("%d\n", t);

     for(int i = ; i < t; i++){

         printf("%d ", ans[i]);

     }

     puts("");

     return ;

 }