#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  char c = getchar();
  long long x = 0;
  bool f = 0;
  for (; !isdigit(c); c = getchar()) f ^= !(c ^ 45);
  for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
  if (f) x = -x;
  return x;
}
const long long inf = 1e18;
const long long M = 2e5 + 10;
long long n, m, a[M], l[M], r[M], ans = 0, p;
vector<long long> v1[M], v2[M];
struct segment_tree {
  struct tree {
    long long tl, tr, val, tag;
  } t[M << 2];
  void pushup(long long k) {
    t[(k)].val = min(t[(k << 1)].val, t[(k << 1 | 1)].val);
  }
  void pushdown(long long k) {
    t[(k << 1)].tag += t[(k)].tag, t[(k << 1 | 1)].tag += t[(k)].tag,
        t[(k << 1)].val += t[(k)].tag, t[(k << 1 | 1)].val += t[(k)].tag;
    t[(k)].tag = 0;
  }
  void build(long long k, long long l, long long r) {
    t[(k)].tl = l, t[(k)].tr = r;
    if (l == r) {
      t[(k)].val = a[l];
      return;
    }
    long long Mid = (l + r) >> 1;
    build(k << 1, l, Mid), build(k << 1 | 1, Mid + 1, r);
    pushup(k);
  }
  void update(long long k, long long l, long long r, long long z) {
    if (t[(k)].tl >= l && t[(k)].tr <= r) {
      t[(k)].tag += z, t[(k)].val += z;
      return;
    }
    if (t[(k)].tl > r || t[(k)].tr < l) return;
    pushdown(k);
    update(k << 1, l, r, z), update(k << 1 | 1, l, r, z);
    pushup(k);
  }
  long long query(long long k, long long l, long long r) {
    if (t[(k)].tl >= l && t[(k)].tr <= r) return t[(k)].val;
    if (t[(k)].tl > r || t[(k)].tr < l) return inf;
    pushdown(k);
    return min(query(k << 1, l, r), query(k << 1 | 1, l, r));
  }
} T;
signed main() {
  n = read(), m = read();
  for (long long i = 1; i <= n; i++) a[i] = read();
  T.build(1, 1, n);
  for (long long i = 1; i <= m; i++)
    l[i] = read(), r[i] = read(), v1[r[i]].push_back(i), v2[l[i]].push_back(i),
    T.update(1, l[i], r[i], -1);
  for (long long i = 1; i <= n; i++) {
    for (long long j = 0; j < v2[i].size(); j++)
      T.update(1, l[v2[i][j]], r[v2[i][j]], 1);
    for (long long j = 0; j < v1[i - 1].size(); j++)
      T.update(1, l[v1[i - 1][j]], r[v1[i - 1][j]], -1);
    if (a[i] - T.query(1, 1, n) > ans) ans = a[i] - T.query(1, 1, n), p = i;
  }
  cout << ans << endl;
  long long cnt = 0;
  for (long long i = 1; i <= m; i++)
    if (l[i] > p || r[i] < p) cnt++;
  cout << cnt << endl;
  for (long long i = 1; i <= m; i++)
    if (l[i] > p || r[i] < p) cout << i << endl;
  return 0;
}
