#include <bits/stdc++.h>
using namespace std;
const double Pi = acos(-1);
int n, q;
int s[int(1e5) + 5], a[int(1e5) + 5];
vector<int> point;
vector<pair<int, int> > seg;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout.tie(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r;
    seg.push_back(pair<int, int>(l, r));
    point.push_back(l);
    point.push_back(r);
  }
  sort(point.begin(), point.end());
  (point).erase(unique(point.begin(), point.end()), (point).end());
  int Pos;
  int ans = *max_element(a + 1, a + 1 + n) - *min_element(a + 1, a + 1 + n);
  for (int i = 0; i < int((point).size()); i++) {
    for (int j = 0; j < q; j++)
      if (point[i] >= seg[j].first && point[i] <= seg[j].second)
        s[seg[j].first]--, s[seg[j].second + 1]++;
    vector<int> f;
    for (int i = 1; i <= n; i++) {
      s[i] += s[i - 1];
      f.push_back(s[i] + a[i]);
    }
    int tmp =
        *max_element(f.begin(), f.end()) - *min_element(f.begin(), f.end());
    if (tmp > ans) {
      ans = tmp;
      Pos = point[i];
    }
    memset(s, 0, sizeof(s));
  }
  cout << ans << '\n';
  vector<int> ans2;
  for (int i = 0; i < q; i++)
    if (Pos >= seg[i].first && Pos <= seg[i].second) ans2.push_back(i);
  cout << int((ans2).size()) << '\n';
  for (int x : ans2) cout << x + 1 << ' ';
  return 0;
}
