#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:667177216")
using namespace std;
const long long MOD = 1000000000 + 7;
const long long MAXN = 2 * 100000 + 100;
int T[4 * MAXN];
int LAZY[4 * MAXN];
void build(vector<int> &a, int v, int tl, int tr) {
  if (tl == tr) {
    T[v] = a[tl];
    LAZY[v] = 0;
    return;
  }
  int tm = (tl + tr) >> 1;
  build(a, 2 * v, tl, tm);
  build(a, 2 * v + 1, tm + 1, tr);
  T[v] = min(T[2 * v] + LAZY[2 * v], T[2 * v + 1] + LAZY[2 * v + 1]);
}
void push(int v) {
  LAZY[2 * v + 1] += LAZY[v];
  LAZY[2 * v] += LAZY[v];
  LAZY[v] = 0;
}
int get_mini(int v, int tl, int tr, int l, int r) {
  if (l > r) return 1e9;
  if (tl == l && tr == r) {
    return T[v] + max(0, LAZY[v]);
  }
  push(v);
  int tm = (tl + tr) >> 1;
  int mini_l = get_mini(2 * v, tl, tm, l, min(tm, r));
  int mini_r = get_mini(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
  T[v] = min(T[2 * v] + LAZY[2 * v], T[2 * v + 1] + LAZY[2 * v + 1]);
  return min(mini_l, mini_r);
}
void update(int v, int tl, int tr, int l, int r, int val) {
  if (l > r) return;
  if (tl == l && tr == r) {
    LAZY[v] += val;
    return;
  }
  push(v);
  int tm = (tl + tr) >> 1;
  update(2 * v, tl, tm, l, min(tm, r), val);
  update(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, val);
  T[v] = min(T[2 * v] + LAZY[2 * v], T[2 * v + 1] + LAZY[2 * v + 1]);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  vector<int> add(n + 1, 0);
  for (int(i) = 0; (i) < n; (i)++) cin >> a[i];
  vector<pair<int, int>> q(m);
  for (int(i) = 0; (i) < m; (i)++)
    cin >> q[i].first >> q[i].second, q[i].first--, q[i].second--;
  vector<vector<int>> starts(n), ends(n);
  for (int i = 0; i < m; ++i) {
    for (int j = q[i].first; j <= q[i].second; ++j) {
      a[j]--;
    }
    starts[q[i].first].push_back(i);
    ends[q[i].second].push_back(i);
  }
  build(a, 1, 0, n - 1);
  int ans = 0;
  int good_i = -1;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < starts[i].size(); ++j) {
      int v = starts[i][j];
      update(1, 0, n - 1, q[v].first, q[v].second, 1);
    }
    int maxi = get_mini(1, 0, n - 1, i, i);
    int mini = get_mini(1, 0, n - 1, 0, n - 1);
    if (ans < maxi - mini) {
      good_i = i;
    }
    ans = max(ans, maxi - mini);
    for (int j = 0; j < ends[i].size(); ++j) {
      int v = ends[i][j];
      update(1, 0, n - 1, q[v].first, q[v].second, -1);
    }
  }
  set<int> answ;
  for (int i = 0; i < m; ++i) answ.insert(i);
  for (int i = 0; i <= good_i; ++i) {
    for (int j = 0; j < starts[i].size(); ++j) {
      int v = starts[i][j];
      answ.erase(v);
    }
    if (i == good_i) break;
    for (int j = 0; j < ends[i].size(); ++j) {
      int v = ends[i][j];
      answ.insert(v);
    }
  }
  cout << ans << endl;
  cout << answ.size() << endl;
  for (auto it : answ) cout << it + 1 << " ";
  return 0;
}
