#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
template <class T>
using V = vector<T>;
const ll inf = (1e18);
const ll mod = 998244353;
const vector<int> dy = {-1, 0, 1, 0}, dx = {0, -1, 0, 1};
ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
ll LCM(ll c, ll d) { return c / GCD(c, d) * d; }
struct __INIT {
  __INIT() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  }
} __init;
template <class T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
void debag(const vector<T> &a) {
  cerr << "debag :";
  for (auto v : a) cerr << v << " ";
  cerr << "\n";
}
template <class T>
void print(const vector<T> &a) {
  for (auto v : a) cout << v << " ";
  cout << "\n";
}
template <typename T, typename E>
struct lazysegtree {
  using F = function<T(T, T)>;
  using G = function<T(T, E)>;
  using H = function<E(E, E)>;
  int n, height;
  F f;
  G g;
  H h;
  T ti;
  E ei;
  vector<T> dat;
  vector<E> laz;
  lazysegtree(F f, G g, H h, T ti, E ei) : f(f), g(g), h(h), ti(ti), ei(ei) {}
  void init(int n_) {
    n = 1;
    height = 0;
    while (n < n_) n <<= 1, height++;
    dat.assign(2 * n, ti);
    laz.assign(2 * n, ei);
  }
  void build(const vector<T> &v) {
    int n_ = v.size();
    init(n_);
    for (int i = 0; i < n_; i++) dat[n + i] = v[i];
    for (int i = n - 1; i; i--)
      dat[i] = f(dat[(i << 1) | 0], dat[(i << 1) | 1]);
  }
  inline T reflect(int k) { return laz[k] == ei ? dat[k] : g(dat[k], laz[k]); }
  inline void eval(int k) {
    if (laz[k] == ei) return;
    laz[(k << 1) | 0] = h(laz[(k << 1) | 0], laz[k]);
    laz[(k << 1) | 1] = h(laz[(k << 1) | 1], laz[k]);
    dat[k] = reflect(k);
    laz[k] = ei;
  }
  inline void thrust(int k) {
    for (int i = height; i; i--) eval(k >> i);
  }
  inline void recalc(int k) {
    while (k >>= 1) dat[k] = f(reflect((k << 1) | 0), reflect((k << 1) | 1));
  }
  void update(int a, int b, E x) {
    thrust(a += n);
    thrust(b += n - 1);
    for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) laz[l] = h(laz[l], x), l++;
      if (r & 1) --r, laz[r] = h(laz[r], x);
    }
    recalc(a);
    recalc(b);
  }
  void set_val(int a, T x) {
    thrust(a += n);
    dat[a] = x;
    laz[a] = ei;
    recalc(a);
  }
  T query(int a, int b) {
    thrust(a += n);
    thrust(b += n - 1);
    T vl = ti, vr = ti;
    for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) vl = f(vl, reflect(l++));
      if (r & 1) vr = f(reflect(--r), vr);
    }
    return f(vl, vr);
  }
};
void solve() {
  auto f = [&](ll a, ll b) { return min(a, b); };
  auto g = [&](ll a, ll b) { return a + b; };
  int n, k;
  cin >> n >> k;
  V<ll> a(n);
  const ll m = -2 * (1e6);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[i] += m;
  }
  lazysegtree<ll, ll> st(f, g, g, inf, 0);
  st.build(a);
  V<V<int>> l(n), r(n);
  V<P> d;
  for (int i = 0; i < k; i++) {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    l[a].emplace_back(b);
    r[b].emplace_back(a);
    st.update(a, b + 1, -1);
    d.emplace_back(a, b);
  }
  ll ans = 0, id = 0;
  for (int i = 0; i < n; i++) {
    for (int v : l[i]) {
      st.update(i, v + 1, 1);
    }
    ll now = st.query(i, i + 1), mi = st.query(0, n);
    if (chmax(ans, now - mi)) {
      id = i;
    }
    for (int v : r[i]) {
      st.update(v, i + 1, -1);
    }
  }
  cout << ans << "\n";
  V<int> res;
  for (int i = 0; i < k; i++) {
    if (!(d[i].first <= id && id <= d[i].second)) {
      res.emplace_back(i + 1);
    }
  }
  cout << res.size() << "\n";
  print(res);
}
int main() {
  int t = 1;
  while (t--) solve();
}
