#include <bits/stdc++.h>
using namespace std;
int yy[100005], id;
int n, m;
int st[100005 * 4], lz[100005 * 4];
int a[100005];
int l[305], r[305];
inline void pu(int rt) { st[rt] = max(st[2 * rt + 1], st[2 * rt + 2]); }
void pd(int rt, int l, int r, int m) {
  if (lz[rt]) {
    int t = lz[rt];
    lz[2 * rt + 1] += t;
    lz[2 * rt + 2] += t;
    st[2 * rt + 1] += t;
    st[2 * rt + 2] += t;
    lz[rt] = 0;
  }
}
void build(int rt, int l, int r) {
  lz[rt] = 0;
  if (l == r) {
    st[rt] = a[l];
    return;
  }
  int mid = (l + r) / 2;
  build(2 * rt + 1, l, mid);
  build(2 * rt + 2, mid + 1, r);
  pu(rt);
}
void ud(int rt, int l, int r, int ul, int ur, int dt) {
  if (l > ur || r < ul) return;
  if (ul <= l && r <= ur) {
    lz[rt] += dt;
    st[rt] += dt;
    return;
  }
  int mid = (l + r) / 2;
  pd(rt, l, r, mid);
  ud(2 * rt + 1, l, mid, ul, ur, dt), ud(2 * rt + 2, mid + 1, r, ul, ur, dt);
  pu(rt);
}
int query(int rt, int l, int r, int ql, int qr) {
  if (l > qr || r < ql) return -(0x3f3f3f3f);
  if (ql <= l && r <= qr) return st[rt];
  int mid = (l + r) / 2;
  pd(rt, l, r, mid);
  return max(query(2 * rt + 1, l, mid, ql, qr),
             query(2 * rt + 2, mid + 1, r, ql, qr));
}
void init() {}
int main() {
  cin >> n >> m;
  int ans = -(0x3f3f3f3f), p = -1;
  int mmx = -(0x3f3f3f3f), mmn = (0x3f3f3f3f);
  for (int i = (1); i <= (n); i++) {
    scanf("%d", a + i);
    mmx = max(a[i], mmx), mmn = min(a[i], mmn);
  }
  if (m == 0) {
    printf("%d\n0", mmx - mmn);
    return 0;
  }
  for (int i = (0); i < (m); i++) scanf("%d%d", l + i, r + i);
  build(0, 1, n);
  for (int i = (1); i <= (n); i++) {
    for (int j = (0); j < (m); j++) {
      if (l[j] == i) {
        ud(0, 1, n, l[j], r[j], -1);
      } else if (i - 1 == r[j]) {
        ud(0, 1, n, l[j], r[j], 1);
      }
    }
    int mx = query(0, 1, n, 1, n);
    int nowmin = query(0, 1, n, i, i);
    if (mx - nowmin > ans) {
      ans = mx - nowmin;
      p = i;
    }
  }
  for (int i = (0); i < (m); i++) {
    if (p >= l[i] && p <= r[i]) {
      yy[id++] = i + 1;
    }
  }
  printf("%d\n%d\n", ans, id);
  for (int i = (0); i < (id); i++) printf("%d ", yy[i]);
  return 0;
}
