#include <algorithm>

#include  <iterator>

#include  <iostream>

#include   <cstring>

#include   <cstdlib>

#include   <iomanip>

#include    <bitset>

#include    <cctype>

#include    <cstdio>

#include    <string>

#include    <vector>

#include     <stack>

#include     <cmath>

#include     <queue>

#include      <list>

#include       <map>

#include       <set>

#include   <cassert>

using namespace std;

#define lson (l , mid , rt << 1)

#define rson (mid + 1 , r , rt << 1 | 1)

#define debug(x) cerr << #x << " = " << x << "\n";

#define pb push_back

#define pq priority_queue

typedef long long ll;

typedef unsigned long long ull;

//typedef __int128 bll;

typedef pair<ll ,ll > pll;

typedef pair<int ,int > pii;

typedef pair<int,pii> p3;

typedef pair<ll,int>pli;

//priority_queue<int> q;//这是一个大根堆q

//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q

#define fi first

#define se second

//#define endl '\n'

//#define R register

#define OKC ios::sync_with_stdio(false);cin.tie(0)

#define FT(A,B,C) for(int A=B;A <= C;++A)  //用来压行

#define REP(i , j , k)  for(int i = j ; i <  k ; ++i)

#define max3(a,b,c) max(max(a,b), c);

#define min3(a,b,c) min(min(a,b), c);

//priority_queue<int ,vector<int>, greater<int> >que;

const ll mos = 0x7FFFFFFF;  //

const ll nmos = 0x80000000;  //-2147483648

const int inf = 0x3f3f3f3f;

const ll inff = 0x3f3f3f3f3f3f3f3f; //18

//const int mod = 1e9+7;

const double esp = 1e-;

const double PI=acos(-1.0);

const double PHI=0.61803399;    //黄金分割点

const double tPHI=0.38196601;

template<typename T>

inline T read(T&x){

    x=;int f=;char ch=getchar();

    while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x=f?-x:x;

}

/*-----------------------showtime---------------------*/

            const int maxn = 1e5+;

            int mx[maxn<<],mn[maxn<<],dif[maxn<<];

            int lazy[maxn<<];

            int a[maxn];

            pii e[maxn];

            void pushup(int rt){

                mx[rt] = max(mx[rt<<], mx[rt<<|]);

                mn[rt] = min(mn[rt<<], mn[rt<<|]);

                dif[rt] = mx[rt] - mn[rt];

            }

            void build(int l,int r,int rt){

                if(l == r){

                    mx[rt] = mn[rt] = a[l];

                    dif[rt] = mx[rt] - mn[rt];

                    return;

                }

                int mid = (l + r) >> ;

                build(l, mid, rt<<);

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

                pushup(rt);

            }

            vector<int>tmp,res;

            void pushdown(int rt){

                if(lazy[rt] == ) return;

                lazy[rt<<] += lazy[rt];

                lazy[rt<<|] += lazy[rt];

                mn[rt<<] += lazy[rt];

                mn[rt<<|] += lazy[rt];

                mx[rt<<] += lazy[rt];

                mx[rt<<|] += lazy[rt];

                lazy[rt] = ;

                return;

            }

            void update(int L, int R ,int c,int l,int r,int rt){

                if(l>=L && r<=R){

                    mx[rt] += c;

                    mn[rt] += c;

                    lazy[rt] += c;

                    return;

                }

                pushdown(rt);

                int mid = (l + r) >> ;

                if(mid >= L)update(L,R,c,l,mid,rt<<);

                if(mid < R)update(L,R,c,mid+,r,rt<<|);

                pushup(rt);

            }

int main(){

            int n,m;

            scanf("%d%d", &n, &m);

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

            build(,n,);

            for(int i=; i<=m; i++) scanf("%d%d", &e[i].fi, &e[i].se);

            int ans = ;

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

                tmp.clear();

                for(int j=; j<=m; j++){

                    if(e[j].fi == i){

                        update(e[j].fi,e[j].se,-,,n,);

                    }

                    else if(e[j].se == i-){

                        update(e[j].fi,e[j].se,,,n,);

                    }

                    if(e[j].fi <=i && e[j].se >= i)

                        tmp.pb(j);

                }

                int q = dif[];

                if(ans < q){

                    ans = q;

                  //  res.clear();

                    res = tmp;

                }

            }

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

            printf("%d\n", (int)res.size());

            for(int i=; i<(int)res.size(); i++){

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

            }

            puts("");

            return ;

}