#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long int ii, jj, k, kk, d, dd, p, pp, n, m, nn, mm, x, y, r, aa, bb, mn,
      mx, c, cc, lst, ans = 0, i, j;
  string s, second, str, sss;
  cin >> n >> m;
  vector<long long int> v[n];
  for (i = 0; i < n; i++) {
    cin >> aa;
    for (j = 0; j < n; j++) {
      v[j].push_back(aa);
    }
  }
  vector<pair<long long int, long long int> > vvv;
  while (m--) {
    cin >> aa >> bb;
    vvv.push_back(make_pair(aa, bb));
    for (i = aa - 1; i < bb; i++) {
      for (j = aa - 1; j < bb; j++) {
        v[i][j]--;
      }
    }
  }
  mx = -1;
  vector<long long int> vv;
  for (i = 0; i < n; i++) {
    long long int mxx = -11000000007;
    long long int mnn = 1000000007;
    for (j = 0; j < (long)v[i].size(); j++) {
      if (v[i][j] > mxx) {
        mxx = v[i][j];
      }
      if (v[i][j] < mnn) {
        mnn = v[i][j];
        ii = j;
      }
    }
    if (abs(mxx - mnn) > mx) {
      mx = abs(mxx - mnn);
      jj = ii;
    }
  }
  cout << mx;
  cout << endl;
  jj++;
  for (i = 0; i < (long)vvv.size(); i++) {
    if (jj >= vvv[i].first && jj <= vvv[i].second) {
      vv.push_back(i + 1);
    }
  }
  cout << (long)vv.size();
  cout << endl;
  for (long long int index = 0; index < vv.size(); index++) {
    cout << vv[index] << " ";
  }
  cout << endl;
  ;
}
