#include <bits/stdc++.h>
using namespace std;
const int inf = 1 << 29;
const long long INF = 1ll << 60;
const double Inf = 1e20;
const double eps = 1e-9;
void gmax(int &a, int b) { a = (a > b ? a : b); }
void gmin(int &a, int b) { a = (a < b ? a : b); }
const int maxn = 100050;
int n, m, l[maxn], r[maxn];
int a[maxn], best, b[maxn], c[maxn], d[maxn];
vector<int> tmp, ans;
int points[maxn], tot;
int main() {
  scanf("%d%d", &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]);
    points[++tot] = (l[i]);
    points[++tot] = (r[i] + 1);
  }
  points[++tot] = (1);
  points[++tot] = (n + 1);
  sort(points + 1, points + tot + 1);
  tot = unique(points + 1, points + tot + 1) - (points + 1);
  for (int i = 1; i <= tot; ++i) {
    b[i] = -inf;
    d[i] = inf;
    for (int j = points[i]; j <= points[i + 1] - 1; ++j)
      b[i] = max(b[i], a[j]), d[i] = min(d[i], a[j]);
  }
  for (int i = 1; i <= m; ++i) {
    r[i]++;
    l[i] = lower_bound(points + 1, points + tot + 1, l[i]) - points;
    r[i] = lower_bound(points + 1, points + tot + 1, r[i]) - points;
  }
  for (int i = 1; i <= tot; ++i)
    if (points[i] <= n) {
      tmp.clear();
      for (int j = 1; j <= tot; ++j) c[j] = 0;
      for (int j = 1; j <= m; ++j)
        if (l[j] <= i && i < r[j]) {
          tmp.push_back(j);
          c[l[j]]--;
          c[r[j]]++;
        }
      for (int j = 1; j <= tot; ++j) c[j] += c[j - 1];
      int vmax = -inf;
      for (int j = 1; j <= tot; ++j) gmax(vmax, c[j] + b[j]);
      if (vmax - (d[i] - ((int)(tmp).size())) > best) {
        best = vmax - (d[i] - ((int)(tmp).size()));
        ans = tmp;
      }
    }
  printf("%d\n", best);
  printf("%d\n", ((int)(ans).size()));
  for (auto p : ans) printf("%d ", p);
  ;
  return 0;
}
