#include <bits/stdc++.h>
#pragma gcc optimize("Ofast")
using namespace std;
inline void input(int &_x) {
  _x = 0;
  int _tmp = 1;
  char _tc = getchar();
  while ((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
  if (_tc == '-') _tc = getchar(), _tmp = -1;
  while (_tc >= '0' && _tc <= '9') _x = _x * 10 + (_tc - 48), _tc = getchar();
  _x *= _tmp;
}
int root[400009], tag[400009];
int aa[100009];
inline void build(int id, int l, int r) {
  if (l == r) {
    root[id] = aa[l];
    return;
  }
  int mid = (l + r) >> 1;
  build((id << 1), l, mid);
  build((id << 1) + 1, mid + 1, r);
  root[id] = max(root[(id << 1)], root[(id << 1) + 1]);
}
inline void push(int id) {
  root[id] += tag[id];
  tag[(id << 1)] += tag[id];
  tag[(id << 1) + 1] += tag[id];
  tag[id] = 0;
}
inline void modify(int id, int l, int r, int ql, int qr, int v) {
  if (tag[id]) push(id);
  if (ql <= l && r <= qr) {
    tag[id] += v;
    push(id);
    return;
  }
  if (qr < l || r < ql) return;
  int mid = (l + r) >> 1;
  modify((id << 1), l, mid, ql, qr, v);
  modify((id << 1) + 1, mid + 1, r, ql, qr, v);
  root[id] = max(root[(id << 1)], root[(id << 1) + 1]);
}
int n, m;
vector<int> seg[100009];
bitset<100009> vis;
inline bool cmp(int a, int b) { return aa[a] < aa[b]; }
signed main() {
  int ma = -1;
  input(n);
  input(m);
  for (int i = 1; i < n + 1; ++i) input(aa[i]), ma = max(ma, aa[i]);
  vector<pair<int, int> > v(m), w;
  for (auto &i : v) input(i.first), input(i.second);
  for (int i = 1; i < n + 1; ++i) w.emplace_back(aa[i], i);
  sort((w).begin(), (w).end());
  int ans = -1, p = 0;
  build(1, 1, n);
  for (int i = 1; i < n + 1; ++i)
    for (int j = 0; j < m; ++j)
      if (v[j].first <= i && i <= v[j].second) seg[i].emplace_back(j);
  for (int _ = 0; _ < n; ++_) {
    int i = w[_].second;
    if (ans > ma - (aa[i] - (int)(seg[i]).size())) continue;
    int cnt = 0;
    for (auto &j : seg[i]) modify(1, 1, n, v[j].first, v[j].second, -1), ++cnt;
    if (root[1] - (aa[i] - cnt) > ans) {
      ans = root[1] - (aa[i] - cnt);
      p = i;
    }
    for (auto &j : seg[i]) modify(1, 1, n, v[j].first, v[j].second, 1);
  }
  cout << ans << '\n' << (int)(seg[p]).size() << '\n';
  for (auto &i : seg[p]) cout << i + 1 << " ";
}
