#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  int n, m, z = 0, a[100328] = {}, l[328] = {}, r[328] = {}, x = 0, y = 0;
  int d[666] = {}, e[666] = {}, d2[666] = {}, e2[666] = {};
  for (int i = 0; i < 666; i++) d[i] = 1000000007, e[i] = -1000000007;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  vector<int> f = {1};
  for (int i = 1; i <= m; i++)
    cin >> l[i] >> r[i], f.push_back(l[i]), f.push_back(r[i] + 1);
  sort(f.begin(), f.end());
  f.push_back(n + 1);
  for (int i = 0; i < m + m + 1; i++) {
    for (int j = f[i]; j < f[i + 1]; j++) {
      if (a[j] < d[i]) d[i] = a[j], d2[i] = j;
      if (a[j] > e[i]) e[i] = a[j], e2[i] = j;
    }
  }
  for (int i = 0; i < m + m + 1; i++)
    for (int j = 0; j <= m + m; j++) {
      int c = 0;
      for (int k = 1; k <= m; k++)
        if (l[k] <= d2[i] && d2[i] <= r[k] && (l[k] > e2[j] || r[k] < e2[j]))
          c++;
      if (e[j] - d[i] + c > z) {
        z = e[j] - d[i] + c;
        x = d2[i];
        y = e2[j];
      }
    }
  vector<int> w;
  for (int k = 1; k <= m; k++)
    if (l[k] <= x && x <= r[k] && (l[k] > y || r[k] < y)) w.push_back(k);
  cout << z << '\n' << w.size() << '\n';
  for (int i : w) cout << i << ' ';
}
