#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 5;
int a[MAX];
pair<int, int> seg[(int)3e2 + 5];
pair<int, int> st[(int)3e2 + 5];
int iSt = 1;
pair<int, int> ed[(int)3e2 + 5];
int iEd = 1;
int ans;
int iOfMaxEl;
int noOfSeg;
int iOfSeg[(int)3e2 + 5];
int n, m;
struct node {
  int v;
  int lazy;
};
node tree[1 << 18];
void propagate(int p) {
  tree[p * 2].v += tree[p].lazy;
  tree[p * 2 + 1].v += tree[p].lazy;
  tree[p * 2 + 1].lazy += tree[p].lazy;
  tree[p * 2].lazy += tree[p].lazy;
  tree[p].lazy = 0;
}
void build_(int p = 1, int st = 1, int ed = MAX) {
  if (st == ed) {
    if (st > n) {
      tree[p].v = 1e9;
      return;
    }
    tree[p].v = a[st];
    return;
  }
  int mid = (st + ed) / 2;
  build_(p * 2, st, mid);
  build_(p * 2 + 1, mid + 1, ed);
  tree[p].v = min(tree[p * 2].v, tree[p * 2 + 1].v);
}
void set_(int v, int l, int r, int p = 1, int st = 1, int ed = MAX) {
  if (l <= st && ed <= r) {
    tree[p].v += v;
    tree[p].lazy += v;
    return;
  }
  if (tree[p].lazy) {
    propagate(p);
  }
  int mid = (st + ed) / 2;
  if (l <= mid) {
    set_(v, l, r, p * 2, st, mid);
  }
  if (r > mid) {
    set_(v, l, r, p * 2 + 1, mid + 1, ed);
  }
  tree[p].v = min(tree[p * 2].v, tree[p * 2 + 1].v);
}
int get_(int l, int r, int p = 1, int st = 1, int ed = MAX) {
  if (l <= st && ed <= r) {
    return tree[p].v;
  }
  if (tree[p].lazy) {
    propagate(p);
  }
  int mid = (st + ed) / 2;
  int vl = 1e9;
  if (l <= mid) {
    vl = min(vl, get_(l, r, p * 2, st, mid));
  }
  if (r > mid) {
    vl = min(vl, get_(l, r, p * 2 + 1, mid + 1, ed));
  }
  tree[p].v = min(tree[p * 2].v, tree[p * 2 + 1].v);
  return vl;
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  build_();
  for (int i = 1; i <= m; i++) {
    scanf("%d %d", &seg[i].first, &seg[i].second);
    st[i] = {seg[i].first, i};
    ed[i] = {seg[i].second, i};
    set_(-1, seg[i].first, seg[i].second);
  }
  sort(st, st + m + 1);
  sort(ed, ed + m + 1);
  for (int i = 1; i <= n; i++) {
    while (iSt <= m && st[iSt].first == i) {
      set_(1, seg[st[iSt].second].first, seg[st[iSt].second].second);
      iSt++;
    }
    while (iEd <= m && ed[iEd].first < i) {
      set_(-1, seg[ed[iEd].second].first, seg[ed[iEd].second].second);
      iEd++;
    }
    int temp = a[i] - get_(1, n);
    if (ans < temp) {
      ans = temp;
      iOfMaxEl = i;
    }
  }
  printf("%d\n", ans);
  for (int i = 1; i <= m; i++) {
    if (seg[i].second < iOfMaxEl || iOfMaxEl < seg[i].first) {
      iOfSeg[noOfSeg++] = i;
    }
  }
  printf("%d\n", noOfSeg);
  for (int i = 0; i < noOfSeg; i++) {
    printf("%d ", iOfSeg[i]);
  }
}
