#include <bits/stdc++.h>

using namespace std;

const int MAXN=1e5+100;

int n,m,a[MAXN],l[310],r[310];

int ans,wh;

vector <int> t,be[MAXN],ed[MAXN];

struct node

{

    int l,r,MAX,MIN,sum,lazy;

}sh[MAXN*4];

void pushup(int x)

{

    sh[x].sum=sh[x+x].sum+sh[x+x+1].sum;

    sh[x].MAX=max(sh[x+x].MAX,sh[x+x+1].MAX);

    sh[x].MIN=min(sh[x+x].MIN,sh[x+x+1].MIN);

}

void pushdown(int x)

{

    if (sh[x].lazy!=0)

    {

        sh[x+x].lazy+=sh[x].lazy;

        sh[x+x+1].lazy+=sh[x].lazy;

        sh[x+x].sum+=sh[x].lazy;

        sh[x+x].MAX+=sh[x].lazy;

        sh[x+x].MIN+=sh[x].lazy;

        sh[x+x+1].sum+=sh[x].lazy;

        sh[x+x+1].MAX+=sh[x].lazy;

        sh[x+x+1].MIN+=sh[x].lazy;

        sh[x].lazy=0;

    }

}

void build(int x,int ll,int rr)

{

    sh[x].l=ll;

    sh[x].r=rr;

    if (ll==rr)

    {

        sh[x].MAX=sh[x].MIN=sh[x].sum=a[ll];

        return;

    }

    int mid;

    mid=(ll+rr)>>1;

    build(x+x,ll,mid);

    build(x+x+1,mid+1,rr);

    pushup(x);

}

void change(int x,int ll,int rr,int k)//区间修改

{

    if (sh[x].l>=ll && sh[x].r<=rr)

    {

        sh[x].sum+=k;

        sh[x].MIN+=k;

        sh[x].MAX+=k;

        sh[x].lazy+=k;

        return;

    }

    pushdown(x);

    int mid;

    mid=(sh[x].l+sh[x].r)>>1;

    if (ll<=mid)

      change(x+x,ll,rr,k);

    if (rr>mid)

      change(x+x+1,ll,rr,k);

    pushup(x);

}

int main()

{

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

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

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

    for (int i=1;i<=m;i++)

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

    build(1,1,n);

    if (n==1)

    {

        printf("0\n0\n");

        return 0;

    }

    for (int i=1;i<=m;i++)

    {

        be[l[i]].push_back(i);//对于结束和开始的节点记录区间

        ed[r[i]].push_back(i);

    }

    ans=sh[1].MAX-sh[1].MIN;

    wh=0;

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

    {

        for (int j=0;j<(int)ed[i-1].size();j++)

        {

            int u;

            u=ed[i-1][j];

            change(1,l[u],r[u],1);//将之前修改的区间对当前无影响改回去

        }

        for (int j=0;j<(int)be[i].size();j++)

        {

            int u;

            u=be[i][j];

            change(1,l[u],r[u],-1);//将新增的区间修改

        }

        pushdown(1);

        pushup(1);

        if (sh[1].MAX-sh[1].MIN>ans)//记录当期的极差

        {

            ans=sh[1].MAX-sh[1].MIN;

            wh=i;

        }

    }

    for (int i=1;i<=m;i++)

    {

        if (l[i]<=wh && r[i]>=wh)

          t.push_back(i);

    }

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

    for (int i=0;i<(int)t.size();i++)

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

    printf("\n");

}