#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
#pragma GCC optimize(2)
int n, m;
int l[MAXN], r[MAXN], val[MAXN];
vector<int> s[MAXN], e[MAXN];
bool tag[MAXN];
struct Segment_Tree {
  struct Node {
    int l, r, tag;
    pair<int, int> value;
  } a[MAXN << 2];
  inline void build(int index, int l, int r) {
    a[index].l = l, a[index].r = r;
    a[index].tag = 0;
    if (l == r) {
      a[index].value = make_pair(val[l], val[l]);
      return;
    }
    int mid = (l + r) >> 1;
    build(index << 1, l, mid);
    build(index << 1 | 1, mid + 1, r);
    update(index);
  }
  inline void update(int index) {
    a[index].value.first =
        min(a[index << 1].value.first, a[index << 1 | 1].value.first);
    a[index].value.second =
        max(a[index << 1].value.second, a[index << 1 | 1].value.second);
  }
  inline void pushdown(int index) {
    a[index << 1].value.first += a[index].tag;
    a[index << 1 | 1].value.first += a[index].tag;
    a[index << 1].value.second += a[index].tag;
    a[index << 1 | 1].value.second += a[index].tag;
    a[index << 1].tag += a[index].tag;
    a[index << 1 | 1].tag += a[index].tag;
    a[index].tag = 0;
  }
  inline void modify(int index, int l, int r, int val) {
    if (a[index].l == l && a[index].r == r) {
      a[index].value.first += val;
      a[index].value.second += val;
      a[index].tag += val;
      return;
    }
    pushdown(index);
    int mid = (a[index].l + a[index].r) >> 1;
    if (mid >= r)
      modify(index << 1, l, r, val);
    else if (mid + 1 <= l)
      modify(index << 1 | 1, l, r, val);
    else {
      modify(index << 1, l, mid, val);
      modify(index << 1 | 1, mid + 1, r, val);
    }
    update(index);
  }
  inline pair<int, int> query() { return a[1].value; }
} SGT;
template <typename T>
inline void chkmax(T &x, T y) {
  x = max(x, y);
}
template <typename T>
inline void chkmin(T &x, T y) {
  x = min(x, y);
}
template <typename T>
inline void read(T &x) {
  T f = 1;
  x = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -f;
  for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
  x *= f;
}
int main() {
  read(n);
  read(m);
  for (register int i = 1; i <= n; i++) read(val[i]);
  SGT.build(1, 1, n);
  for (register int i = 1; i <= m; i++) {
    read(l[i]);
    read(r[i]);
    s[l[i]].push_back(r[i]);
    e[r[i]].push_back(l[i]);
    SGT.modify(1, l[i], r[i], -1);
  }
  int mx = 0, loc = 0;
  for (register int i = 1; i <= n; i++) {
    for (unsigned j = 0; j < s[i].size(); j++) SGT.modify(1, i, s[i][j], 1);
    pair<int, int> tmp = SGT.query();
    if (tmp.second - tmp.first > mx) {
      mx = tmp.second - tmp.first;
      loc = i;
    }
    for (unsigned j = 0; j < e[i].size(); j++) SGT.modify(1, e[i][j], i, -1);
  }
  cout << mx << '\n';
  vector<int> res;
  for (int i = 1; i <= m; i++) {
    if (l[i] > loc || r[i] < loc) res.push_back(i);
  }
  cout << (int)res.size() << '\n';
  for (unsigned i = 0; i < res.size(); i++) cout << res[i] << ' ';
  cout << '\n';
  return 0;
}
