#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int inf = 1e8;
int tree[4 * N + 100], lazy[4 * N + 100], a[N + 100];
vector<int> fr[N + 100], rv[N + 100];
int le[N + 100], ri[N + 100];
void build(int v, int tl, int tr) {
  if (tl == tr) {
    tree[v] = a[tl];
  } else {
    int tm = (tl + tr) / 2;
    build(v * 2, tl, tm);
    build(v * 2 + 1, tm + 1, tr);
    tree[v] = min(tree[v * 2], tree[v * 2 + 1]);
  }
}
void push(int v) {
  tree[v * 2] += lazy[v];
  tree[v * 2 + 1] += lazy[v];
  lazy[v * 2] += lazy[v];
  lazy[v * 2 + 1] += lazy[v];
  lazy[v] = 0;
}
void update(int v, int tl, int tr, int l, int r, int val) {
  if (l > r) return;
  if (tl == l && tr == r) {
    tree[v] += val;
    lazy[v] += val;
  } else {
    push(v);
    int tm = (tl + tr) / 2;
    update(v * 2, tl, tm, l, min(r, tm), val);
    update(v * 2 + 1, tm + 1, tr, max(tm + 1, l), r, val);
    tree[v] = min(tree[v * 2], tree[v * 2 + 1]);
  }
}
int getMin(int v, int tl, int tr, int l, int r) {
  if (l > r) return inf;
  if (tl == l && tr == r) {
    return tree[v];
  }
  push(v);
  int tm = (tl + tr) / 2;
  return min(getMin(v * 2, tl, tm, l, min(r, tm)),
             getMin(v * 2 + 1, tm + 1, tr, max(tm + 1, l), r));
}
int main() {
  int n, m;
  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", le + i, ri + i);
    fr[le[i]].push_back(ri[i]);
    rv[ri[i]].push_back(le[i]);
  }
  build(1, 1, n);
  for (int i = 1; i <= m; i++) {
    update(1, 1, n, le[i], ri[i], -1);
  }
  int ans = 0, idx = 0;
  for (int i = 1; i <= n; i++) {
    for (auto it : fr[i]) {
      update(1, 1, n, i, it, 1);
    }
    int cur = getMin(1, 1, n, 1, i - 1);
    cur = min(cur, getMin(1, 1, n, i + 1, n));
    if (a[i] - cur >= ans) {
      ans = a[i] - cur;
      idx = i;
    }
    for (auto it : rv[i]) {
      update(1, 1, n, it, i, -1);
    }
  }
  printf("%d\n", ans);
  vector<int> seq;
  for (int i = 1; i <= m; i++) {
    if (le[i] <= idx && ri[i] >= idx) {
      continue;
    } else {
      seq.push_back(i);
    }
  }
  printf("%d\n", (int)seq.size());
  for (auto it : seq) {
    printf("%d ", it);
  }
  printf("\n");
}
