#include <bits/stdc++.h>
using namespace std;
const int N = (int)1e5 + 10;
const int M = (int)302;
int n, m, v[N], tr[4 * N], lz[4 * N], L[N], R[N];
vector<int> in[N], out[N];
inline void propagate(int no, int l, int r) {
  if (!lz[no]) return;
  tr[no] += lz[no];
  if (l != r) {
    int nxt = (no << 1);
    lz[nxt] += lz[no];
    lz[nxt + 1] += lz[no];
  }
  lz[no] = 0;
}
void build(int no, int l, int r) {
  if (l == r) {
    tr[no] = v[l];
    return;
  }
  int nxt = (no << 1), mid = (l + r) >> 1;
  build(nxt, l, mid);
  build(nxt + 1, mid + 1, r);
  tr[no] = min(tr[nxt], tr[nxt + 1]);
}
int query(int no, int l, int r, int i, int j) {
  propagate(no, l, r);
  if (r < i || l > j) return (int)1e8;
  if (l >= i && r <= j) return tr[no];
  int nxt = (no << 1), mid = (l + r) >> 1;
  return min(query(nxt, l, mid, i, j), query(nxt + 1, mid + 1, r, i, j));
}
void update(int no, int l, int r, int i, int j, int x) {
  propagate(no, l, r);
  if (r < i || l > j) return;
  if (l >= i && r <= j) {
    lz[no] += x;
    propagate(no, l, r);
    return;
  }
  int nxt = (no << 1), mid = (l + r) >> 1;
  update(nxt, l, mid, i, j, x);
  update(nxt + 1, mid + 1, r, i, j, x);
  tr[no] = min(tr[nxt], tr[nxt + 1]);
}
inline int query(int l, int r) { return query(1, 1, n, l, r); }
inline void update(int l, int r, int x) { update(1, 1, n, l, r, x); }
bitset<M> foo;
bitset<M> sol;
inline void add(int id) {
  for (int i = 0; i < in[id].size(); ++i) {
    int s = in[id][i];
    sol.flip(s);
    update(L[s], R[s], 1);
  }
}
inline void rem(int id) {
  for (int i = 0; i < out[id].size(); ++i) {
    int s = out[id][i];
    sol.flip(s);
    update(L[s], R[s], -1);
  }
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", v + i);
  }
  build(1, 1, n);
  for (int i = 1; i <= m; ++i) {
    scanf("%d %d", L + i, R + i);
    in[L[i]].push_back(i);
    out[R[i]].push_back(i);
    update(L[i], R[i], -1);
  }
  int ans = (int)-1e8;
  for (int i = 1; i <= n; ++i) {
    add(i);
    int bst = query(1, n);
    if (ans < v[i] - bst) {
      ans = v[i] - bst;
      sol = foo;
    }
    rem(i);
  }
  printf("%d\n", ans);
  vector<int> show;
  for (int i = 1; i <= m; ++i) {
    if (!sol[i]) show.push_back(i);
  }
  printf("%d\n", (int)show.size());
  for (int i = 0; i < (int)show.size(); ++i) {
    if (i) printf(" ");
    printf("%d", show[i]);
  }
  printf("\n");
  return 0;
}
