#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2")
using namespace std;
const int inf = 1e9;
int Solve(int n, int m, vector<int> &mins, vector<int> &l, vector<int> &r,
          int ind, int max_val, vector<int> &ans) {
  vector<int> extra(n + 1, 0);
  for (int i = 0; i < m; i++) {
    if (l[i] > ind || r[i] < ind) {
      ans.push_back(i);
      extra[l[i]]--;
      extra[r[i] + 1]++;
    }
  }
  int min_val = inf, cur_extra = 0;
  for (int i = 0; i < n; i++) {
    cur_extra += extra[i];
    min_val = min(min_val, mins[i] + cur_extra);
  }
  return max_val - min_val;
}
int main() {
  cin.tie(NULL);
  cout.tie(NULL);
  ios_base::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  vector<int> val(n);
  for (int i = 0; i < n; i++) {
    cin >> val[i];
  }
  vector<int> l(m), r(m);
  vector<int> is_used(n + 1, false);
  for (int i = 0; i < m; i++) {
    cin >> l[i] >> r[i];
    l[i]--, r[i]--;
    is_used[l[i]] = true;
    is_used[r[i] + 1] = true;
  }
  unordered_map<int, int> old_to_new;
  old_to_new.reserve(1 << 12);
  vector<int> mins = {inf}, maxs = {-inf};
  int cur_i = 0;
  for (int i = 0; i < n; i++) {
    if (is_used[i]) {
      if (mins[cur_i] != inf) {
        cur_i++;
        mins.push_back(inf);
        maxs.push_back(-inf);
      }
      old_to_new[i] = cur_i;
    }
    mins[cur_i] = min(mins[cur_i], val[i]);
    maxs[cur_i] = max(maxs[cur_i], val[i]);
  }
  if (is_used[n]) {
    old_to_new[n] = mins.size();
  }
  vector<int> new_l(m), new_r(m);
  for (int i = 0; i < m; i++) {
    new_l[i] = old_to_new[l[i]];
    new_r[i] = old_to_new[r[i] + 1] - 1;
  }
  n = mins.size();
  int max_diff = -inf;
  vector<int> ans;
  for (int i = 0; i < n; i++) {
    vector<int> cur_ans;
    int cur_diff = Solve(n, m, mins, new_l, new_r, i, maxs[i], cur_ans);
    if (max_diff < cur_diff) {
      max_diff = cur_diff;
      ans = vector<int>(cur_ans);
    }
  }
  cout << max_diff << '\n';
  cout << ans.size() << '\n';
  for (int a : ans) {
    cout << a + 1 << ' ';
  }
  cout << '\n';
}
