#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9, N = 1e5 + 15;
int a[N], add[N], ans[N], mn, n, m;
vector<int> lft[N], rgt[N], done;
vector<pair<int, int> > queries;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < m; i++) {
    int l, r;
    cin >> l >> r;
    l--;
    r--;
    lft[l].push_back(r);
    rgt[r].push_back(l);
    queries.push_back({l, r});
  }
  mn = a[0];
  for (int i = 0; i < n; i++) ans[i] = -inf;
  for (int i = 0; i < n; i++) {
    ans[i] = max(ans[i], a[i] - mn);
    for (int l : rgt[i]) {
      for (int j = l; j <= i; j++) {
        add[j]--;
        mn = min(mn, a[j] + add[j]);
      }
    }
    mn = min(mn, a[i] + add[i]);
  }
  mn = a[n - 1];
  for (int i = 0; i < n; i++) add[i] = 0;
  for (int i = n - 1; i >= 0; i--) {
    ans[i] = max(ans[i], a[i] - mn);
    for (int r : lft[i]) {
      for (int j = i; j <= r; j++) {
        add[j]--;
        mn = min(mn, a[j] + add[j]);
      }
    }
    mn = min(mn, a[i] + add[i]);
  }
  int val = *max_element(ans, ans + n);
  for (int i = 0; i < n; i++) {
    if (ans[i] == val) {
      for (int j = 0; j < m; j++) {
        if (queries[j].first <= i && queries[j].second >= i) continue;
        done.push_back(j + 1);
      }
      break;
    }
  }
  cout << val << '\n' << (int)done.size() << '\n';
  for (auto x : done) cout << x << ' ';
  cout << '\n';
  return 0;
}
