#include <bits/stdc++.h>
using namespace std;
int n, m, a[1000], l[1000], r[1000], mn, mx, ans, mx2, mn2, ansi = -1, ans2;
string s;
int main() {
  ios::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if (i == 0) mn = a[i], mx = a[i];
    mn = min(mn, a[i]), mx = max(a[i], mx), ans = mx - mn;
  }
  for (int j = 0; j < m; j++) cin >> l[j] >> r[j];
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < m; j++) {
      if (i >= l[j] && i <= r[j]) {
        for (int k = l[j] - 1; k < r[j]; k++) {
          a[k]--;
        }
      }
    }
    for (int j = 0; j < n; j++) {
      if (j == 0) mn2 = a[j], mx2 = a[j];
      mn2 = min(mn2, a[j]), mx2 = max(a[j], mx2);
    }
    if (ans < mx2 - mn2) ans = mx2 - mn2, ansi = i;
    for (int j = 0; j < m; j++) {
      if (i >= l[j] && i <= r[j]) {
        for (int k = l[j] - 1; k < r[j]; k++) {
          a[k]++;
        }
      }
    }
  }
  cout << ans << endl;
  for (int i = 0; i < m; i++) {
    if (ansi >= l[i] && ansi <= r[i]) {
      ans2++;
    }
  }
  cout << ans2 << endl;
  for (int i = 0; i < m; i++) {
    if (ansi >= l[i] && ansi <= r[i]) {
      cout << i + 1 << " ";
    }
  }
}
