#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 100005;
int a[maxn];
struct tree {
  int m, lazy;
} T[maxn << 2];
inline void pushdown(int u, int l, int r) {
  if (T[u].lazy) {
    int mid = (l + r) >> 1;
    T[u << 1].m += T[u].lazy;
    T[u << 1 | 1].m += T[u].lazy;
    T[u << 1].lazy += T[u].lazy;
    T[u << 1 | 1].lazy += T[u].lazy;
    T[u].lazy = 0;
  }
}
void build(int u, int l, int r) {
  T[u].lazy = 0;
  if (l == r) {
    T[u].m = a[l];
  } else {
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    T[u].m = min(T[u << 1].m, T[u << 1 | 1].m);
  }
}
void change(int u, int l, int r, int cl, int cr, int x) {
  if (cl <= l && r <= cr) {
    T[u].m += x;
    T[u].lazy += x;
    return;
  }
  pushdown(u, l, r);
  int mid = (l + r) >> 1;
  if (cl <= mid) change(u << 1, l, mid, cl, cr, x);
  if (cr > mid) change(u << 1 | 1, mid + 1, r, cl, cr, x);
  T[u].m = min(T[u << 1].m, T[u << 1 | 1].m);
}
int query(int u, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) return T[u].m;
  pushdown(u, l, r);
  int mid = (l + r) >> 1;
  int res = INF;
  if (ql <= mid) res = min(res, query(u << 1, l, mid, ql, qr));
  if (qr > mid) res = min(res, query(u << 1 | 1, mid + 1, r, ql, qr));
  return res;
}
int l[maxn], r[maxn];
int anss[305], flag[305];
int main() {
  int n, m;
  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]);
  int ans = -INF;
  build(1, 1, n);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (l[j] <= i && i <= r[j] && flag[j]) {
        change(1, 1, n, l[j], r[j], 1);
        flag[j] = 0;
      }
      if ((l[j] > i || i > r[j]) && flag[j] == 0) {
        flag[j] = 1;
        change(1, 1, n, l[j], r[j], -1);
      }
    }
    int g = query(1, 1, n, 1, n);
    if (ans < a[i] - g) {
      ans = a[i] - g;
      memcpy(anss, flag, sizeof anss);
    }
  }
  printf("%d\n", ans);
  int cnt = 0;
  for (int i = 1; i <= m; i++)
    if (anss[i]) cnt++;
  printf("%d\n", cnt);
  for (int i = 1; i <= m; i++)
    if (anss[i]) printf("%d ", i);
  printf("\n");
  return 0;
}
