#include <bits/stdc++.h>
using namespace std;
void hello() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout.setf(ios::fixed);
  cout.precision(5);
}
const long long INF = 1e9;
signed main() {
  hello();
  long long n, m;
  cin >> n >> m;
  vector<long long> a(n);
  for (long long i = 0; i < n; ++i) cin >> a[i];
  vector<pair<long long, long long> > b(m);
  vector<vector<long long> > left(n), right(n);
  for (long long i = 0; i < m; ++i) {
    cin >> b[i].first >> b[i].second;
    b[i].first--, b[i].second--;
    left[b[i].second].push_back(b[i].first);
    right[b[i].first].push_back(b[i].second);
  }
  long long min_elem = a[0];
  vector<long long> ans(n, -INF), add(n, 0);
  for (long long i = 0; i < n; ++i) {
    ans[i] = max(ans[i], a[i] - min_elem);
    for (auto ind : left[i])
      for (long long j = ind; j <= i; ++j) {
        add[j]--;
        min_elem = min(min_elem, a[j] + add[j]);
      }
    min_elem = min(min_elem, a[i] + add[i]);
  }
  add.assign(n, 0);
  min_elem = a[n - 1];
  for (long long i = n - 1; i >= 0; --i) {
    ans[i] = max(ans[i], a[i] - min_elem);
    for (auto ind : right[i])
      for (long long j = i; j <= ind; ++j) {
        add[j]--;
        min_elem = min(min_elem, a[j] + add[j]);
      }
    min_elem = min(min_elem, a[i] + add[i]);
  }
  long long res = *max_element(ans.begin(), ans.end());
  vector<long long> segments;
  for (long long i = 0; i < n; ++i)
    if (ans[i] == res) {
      for (long long j = 0; j < m; ++j)
        if (!(b[j].first <= i && i <= b[j].second)) segments.push_back(j);
      break;
    }
  cout << res << "\n" << segments.size() << "\n";
  for (auto item : segments) cout << item + 1 << " ";
  cout << "\n";
  return 0;
}
