#include <bits/stdc++.h>
using namespace std;
const int N = 100006, M = 306;
int n, m, a[N], l[M], r[M];
int b[M << 1], tot, mx[M << 1], mn[M << 1], c[M << 1];
vector<int> ans[M << 1];
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= m; i++) {
    scanf("%d %d", &l[i], &r[i]);
    b[++tot] = l[i];
    b[++tot] = ++r[i];
  }
  b[++tot] = 1;
  b[++tot] = n + 1;
  sort(b + 1, b + tot + 1);
  tot = unique(b + 1, b + tot + 1) - (b + 1);
  for (int i = 1; i <= m; i++) {
    l[i] = lower_bound(b + 1, b + tot + 1, l[i]) - b;
    r[i] = lower_bound(b + 1, b + tot + 1, r[i]) - b;
  }
  for (int i = 1; i < tot; i++) {
    mx[i] = mn[i] = a[b[i]];
    for (int j = b[i] + 1; j < b[i + 1]; j++) {
      mx[i] = max(mx[i], a[j]);
      mn[i] = min(mn[i], a[j]);
    }
  }
  int num = 0, now;
  for (int x = 1; x < tot; x++) {
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= m; i++) {
      if (l[i] <= x && r[i] > x) continue;
      --c[l[i]];
      ++c[r[i]];
      ans[x].push_back(i);
    }
    int s = 0, t = 0, k;
    for (int i = 1; i < tot; i++) {
      s += c[i];
      if (!t || mn[i] + s < k) k = mn[t = i] + s;
    }
    if (!num || mx[x] - k > now) now = mx[num = x] - k;
  }
  cout << now << endl << ans[num].size() << endl;
  for (unsigned int i = 0; i < ans[num].size(); i++) printf("%d ", ans[num][i]);
  puts("");
  return 0;
}
