#include <bits/stdc++.h>
using namespace std;
int n, m, a[100005], l[500], r[500], mx, mn, ans;
set<int> s, res;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  mn = *min_element(a + 1, a + n + 1);
  mx = *max_element(a + 1, a + n + 1);
  ans = mx - mn;
  for (int i = 1; i <= m; i++) cin >> l[i] >> r[i];
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (l[j] == i) {
        for (int k = l[j]; k <= r[j]; k++) a[k]--;
        s.insert(j);
        mn = *min_element(a + 1, a + n + 1);
        mx = *max_element(a + 1, a + n + 1);
      }
    }
    if (mx - mn > ans) {
      ans = mx - mn;
      res = s;
    }
    for (int j = 1; j <= m; j++) {
      if (r[j] == i) {
        for (int k = l[j]; k <= r[j]; k++) a[k]++;
        s.erase(s.find(j));
      }
    }
  }
  cout << ans << endl << res.size() << endl;
  if (res.size() > 0)
    for (auto x : res) cout << x << " ";
  return 0;
}
