#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int a[maxn];
int back[maxn];
int sum[maxn];
int lef[maxn];
int rig[maxn];
int main() {
  std::ios::sync_with_stdio(false);
  int n, m;
  int mi = INF;
  int mx = -INF;
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    mi = min(mi, a[i]);
    mx = max(mx, a[i]);
  }
  int ans = mx - mi;
  memcpy(back, a, sizeof(back));
  vector<int> seg;
  for (int i = 1; i <= m; ++i) {
    cin >> lef[i] >> rig[i];
    seg.push_back(lef[i]);
  }
  seg.erase(unique(seg.begin(), seg.end()), seg.end());
  vector<int> choose;
  for (auto p : seg) {
    vector<int> tmp;
    memset(sum, 0, sizeof(sum));
    memcpy(a, back, sizeof(a));
    mx = -INF;
    mi = INF;
    for (int i = 1; i <= m; ++i) {
      if (lef[i] <= p && rig[i] >= p) {
        sum[lef[i]]--;
        sum[rig[i] + 1]++;
        tmp.push_back(i);
      }
    }
    for (int i = 1; i <= n; ++i) {
      sum[i] += sum[i - 1];
      a[i] += sum[i];
      mx = max(mx, a[i]);
      mi = min(mi, a[i]);
    }
    if (mx - mi > ans) {
      ans = mx - mi;
      choose = tmp;
    }
  }
  cout << ans << endl;
  cout << choose.size() << endl;
  for (auto v : choose) {
    cout << v << " ";
  }
  cout << endl;
  return 0;
}
