#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
const int N = 2e5 + 2, inf = 1e9;
int t[4 * N], a[N], add[4 * N], p[N], s[N], n;
vector<int> lt[N], rt[N], res;
vector<pair<int, int> > q;
void build(int v, int l, int r) {
  if (l == r - 1) {
    t[v] = a[l];
    return;
  }
  int m = (r + l) / 2;
  build(2 * v, l, m);
  build(2 * v + 1, m, r);
  t[v] = min(t[2 * v], t[2 * v + 1]);
}
void push(int v, int l, int r) {
  if (!add[v]) return;
  t[v] += add[v];
  if (l != r - 1) {
    add[2 * v] += add[v];
    add[2 * v + 1] += add[v];
  }
  add[v] = 0;
}
void update(int v, int l, int r, int vl, int vr, int val) {
  push(v, l, r);
  if (l >= vr || vl >= r) return;
  if (l >= vl && r <= vr) {
    add[v] += val;
    push(v, l, r);
    return;
  }
  int m = (r + l) / 2;
  update(2 * v, l, m, vl, vr, val);
  update(2 * v + 1, m, r, vl, vr, val);
  t[v] = min(t[2 * v], t[2 * v + 1]);
}
int get() {
  push(1, 0, n);
  return t[1];
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int m, l, r, ans = -inf, it = 0, c;
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> a[i];
  build(1, 0, n);
  for (int i = 0; i < m; i++) {
    cin >> l >> r;
    l--, r--;
    q.push_back({l, r});
    rt[l].push_back(r);
    lt[r].push_back(l);
  }
  for (int i = 0; i < n; i++) {
    p[i] = get();
    for (auto u : lt[i]) {
      update(1, 0, n, u, i + 1, -1);
    }
  }
  build(1, 0, n);
  memset(add, 0, sizeof add);
  for (int i = n - 1; i >= 0; i--) {
    s[i] = get();
    for (auto u : rt[i]) {
      update(1, 0, n, i, u + 1, -1);
    }
  }
  for (int i = 0; i < n; i++) {
    c = min(p[i], s[i]);
    if (a[i] - c > ans) {
      ans = a[i] - c;
      it = i;
    }
  }
  for (int i = 0; i < q.size(); i++) {
    auto u = q[i];
    l = u.first, r = u.second;
    if (l > it || r < it) res.push_back(i);
  }
  for (int i = 0; i < n; i++) {
    for (auto u : res) {
      l = q[u].first;
      r = q[u].second;
      if (i >= l && i <= r) {
        a[i]--;
      }
    }
  }
  ans = inf;
  for (int i = 0; i < n; i++) {
    if (a[i] < ans) ans = a[i];
  }
  cout << a[it] - ans << endl;
  cout << res.size() << endl;
  for (auto u : res) cout << u + 1 << ' ';
  return 0;
}
