#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const long long _INF = 0xc0c0c0c0c0c0c0c0;
const long long mod = (int)1e9 + 7;
const int N = 1e5 + 100;
int Wa() { return rand() % 2; }
void Hack(int n) {
  srand(time(0));
  int hack = 0;
  for (int j = 1; j <= n; ++j) hack += Wa();
  if (hack == n) puts("OH No!");
}
int n, m;
pair<int, int> p[N];
int Mn[N << 2], lz[N << 2];
int a[N];
void PushUp(int rt) { Mn[rt] = min(Mn[rt << 1], Mn[rt << 1 | 1]); }
void Build(int l, int r, int rt) {
  if (l == r) {
    Mn[rt] = a[l];
    return;
  }
  int m = l + r >> 1;
  Build(l, m, rt << 1);
  Build(m + 1, r, rt << 1 | 1);
  PushUp(rt);
}
void PushDown(int rt) {
  if (lz[rt]) {
    lz[rt << 1] += lz[rt];
    lz[rt << 1 | 1] += lz[rt];
    Mn[rt << 1] += lz[rt];
    Mn[rt << 1 | 1] += lz[rt];
    lz[rt] = 0;
  }
}
void Update(int L, int R, int C, int l, int r, int rt) {
  if (L <= l && r <= R) {
    Mn[rt] += C;
    lz[rt] += C;
    return;
  }
  PushDown(rt);
  int m = l + r >> 1;
  if (L <= m) Update(L, R, C, l, m, rt << 1);
  if (m < R) Update(L, R, C, m + 1, r, rt << 1 | 1);
  PushUp(rt);
}
vector<int> Lp[N], Rp[N];
void Ac() {
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  Build(1, n, 1);
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &p[i].first, &p[i].second);
    Lp[p[i].first].push_back(p[i].second);
    Rp[p[i].second].push_back(p[i].first);
    Update(p[i].first, p[i].second, -1, 1, n, 1);
  }
  int ans = 0, id;
  for (int i = 1; i <= n; ++i) {
    for (int j : Rp[i - 1]) Update(j, i - 1, -1, 1, n, 1);
    for (int j : Lp[i]) Update(i, j, 1, 1, n, 1);
    int tmp = a[i] - Mn[1];
    if (tmp > ans) ans = tmp, id = i;
  }
  printf("%d\n", ans);
  int cnt = 0;
  for (int j = 1; j <= m; ++j) {
    if (id < p[j].first || p[j].second < id) cnt++;
  }
  printf("%d\n", cnt);
  for (int j = 1; j <= m; ++j) {
    if (id < p[j].first || p[j].second < id) printf("%d ", j);
  }
}
int main() {
  while (~scanf("%d%d", &n, &m)) {
    Ac();
  }
  return 0;
}
