#include <bits/stdc++.h>
using namespace std;
int read() {
  int nm = 0, f = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -1;
  for (; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
  return nm * f;
}
struct Note {
  int l, r, pl, v, id;
  bool operator<(const Note &b) const { return this->pl < b.pl; }
} sta[100010 << 3];
int tp;
const int inf = 0x3e3e3e3e;
int id[100010 << 2], maxx[100010 << 2], laz[100010 << 2], pa[100010];
int ans[100010];
void add(int now, int x) {
  laz[now] += x;
  maxx[now] += x;
}
int pllll = 0;
int as = -inf;
int main() {
  maxx[0] = -inf;
  int n = read(), q = read();
  for (int i = 1; i <= n; i++) ans[i] = read();
  for (int i = 1; i <= q; i++) {
    int l = read(), r = read();
    tp++;
    sta[tp].l = l, sta[tp].r = r;
    sta[tp].v = -1;
    sta[tp].pl = l;
    sta[tp].id = i;
    tp++;
    sta[tp] = sta[tp - 1];
    sta[tp].v = 1;
    sta[tp].pl = r + 1;
    sta[tp].id = 0;
  }
  sort(sta + 1, sta + tp + 1);
  int now = 1;
  int mama = -inf;
  for (int i = 1; i <= n; i++) {
    int f = 0;
    while (now <= tp && sta[now].pl == i) {
      f = 1;
      int l = sta[now].l, r = sta[now].r, v = sta[now].v;
      for (int j = l; j <= r; j++) ans[j] += v;
      now++;
    }
    if (f || i == 1) {
      mama = -inf;
      for (int j = 1; j <= n; j++) {
        mama = max(mama, ans[j]);
      }
    }
    if (as < mama - ans[i]) pllll = i;
    as = max(as, mama - ans[i]);
  }
  int tmp = as;
  while (now <= tp) {
    int l = sta[now].l, r = sta[now].r, v = sta[now].v;
    for (int j = l; j <= r; j++) ans[j] += v;
    now++;
  }
  now = 1;
  int i = pllll;
  cout << as << "\n";
  int tot = 0;
  for (int j = 1; j <= tp; j++) {
    if (sta[j].l <= i && sta[j].r >= i) tot++;
  }
  tot >>= 1;
  cout << tot << "\n";
  if (tot == 0) return 0;
  for (int j = 1; j <= tp; j++) {
    if (sta[j].l <= i && sta[j].r >= i && sta[j].id) cout << sta[j].id << " ";
  }
  cout << "\n";
  return 0;
}
