#include <bits/stdc++.h>
using namespace std;
int a[330];
vector<int> v[310];
int ans[310];
int l[310], r[310];
int main() {
  int n, m, i, ma = -1e7, mi = 1e7, k, j;
  cin >> n >> m;
  for (i = 1; i <= n; i++) {
    cin >> a[i];
    ma = max(ma, a[i]);
    mi = min(mi, a[i]);
  }
  ans[0] = ma - mi;
  for (i = 1; i <= m; i++) cin >> l[i] >> r[i];
  for (i = 1; i <= n; i++) {
    ma = -1e7, mi = 1e7;
    for (j = 1; j <= m; j++)
      if (l[j] > i || r[j] < i) {
        for (k = l[j]; k <= r[j]; k++) a[k]--;
        v[i].push_back(j);
      }
    for (j = 1; j <= n; j++) {
      ma = max(ma, a[j]);
      mi = min(mi, a[j]);
    }
    for (j = 1; j <= m; j++)
      if (l[j] > i || r[j] < i)
        for (k = l[j]; k <= r[j]; k++) a[k]++;
    ans[i] = ma - mi;
  }
  int aaa = ans[0], pos = 0;
  for (i = 1; i <= n; i++)
    if (aaa < ans[i]) {
      pos = i;
      aaa = ans[i];
    }
  cout << ans[pos] << endl;
  cout << v[pos].size() << endl;
  if (!v[pos].empty())
    for (i = 0; i < v[pos].size(); i++) cout << v[pos][i] << " ";
  cout << endl;
}
