#include <bits/stdc++.h>
using namespace std;
int n, m;
int A[100006], L[100006], R[100006], maxn, secn;
int S[100006 << 2], lz[100006 << 2];
inline void pushup(int rt) { S[rt] = max(S[rt << 1], S[rt << 1 | 1]); }
void pushdown(int rt, int m) {
  if (lz[rt]) {
    S[rt << 1] += lz[rt], S[rt << 1 | 1] += lz[rt];
    lz[rt << 1] += lz[rt], lz[rt << 1 | 1] += lz[rt];
    lz[rt] = 0;
  }
}
void build(int rt, int l, int r) {
  if (l == r) {
    S[rt] = A[l];
    return;
  }
  int m = l + r >> 1;
  build(rt << 1, l, m), build(rt << 1 | 1, m + 1, r);
  pushup(rt);
}
void modify(int rt, int l, int r, int L, int R, int c) {
  if (L <= l && R >= r) {
    lz[rt] += c, S[rt] += c;
    return;
  }
  pushdown(rt, r - l + 1);
  int m = l + r >> 1;
  if (m >= L) modify(rt << 1, l, m, L, R, c);
  if (m < R) modify(rt << 1 | 1, m + 1, r, L, R, c);
  pushup(rt);
}
int work(int rt, int l, int r, int p) {
  if (l == r && p == l) return S[rt];
  pushdown(rt, r - l + 1);
  int m = l + r >> 1;
  if (p <= m)
    return work(rt << 1, l, m, p);
  else
    return work(rt << 1 | 1, m + 1, r, p);
}
int ANS[100006], p;
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &A[i]);
  }
  build(1, 1, n);
  for (int i = 0; i < m; ++i) scanf("%d%d", &L[i], &R[i]);
  for (int j = 0; j < m; ++j)
    if (L[j] == 1) modify(1, 1, n, L[j], R[j], -1);
  int ans = S[1] - work(1, 1, n, 1), Ans = 1;
  for (int x = 2; x <= n; ++x) {
    for (int j = 0; j < m; ++j) {
      if (L[j] == x) modify(1, 1, n, L[j], R[j], -1);
      if (R[j] == x - 1) modify(1, 1, n, L[j], R[j], 1);
    }
    int cur = S[1] - work(1, 1, n, x);
    if (cur > ans) Ans = x;
    ans = max(ans, cur);
  }
  cout << ans << endl;
  for (int j = 0; j < m; ++j)
    if (L[j] <= Ans && R[j] >= Ans) ANS[++p] = j + 1;
  cout << p << endl;
  for (int i = 1; i <= p; ++i) cout << ANS[i] << ' ';
  return 0;
}
