#include <bits/stdc++.h>
using namespace std;
template <class T, size_t n>
ostream &operator<<(ostream &os, array<T, n> V) {
  os << "[";
  for (auto vv : V) os << vv << ",";
  return os << "]";
}
template <class L, class R>
ostream &operator<<(ostream &os, pair<L, R> P) {
  return os << "(" << P.first << "," << P.second << ")";
}
template <class T>
ostream &operator<<(ostream &os, set<T> V) {
  os << "[";
  for (auto vv : V) os << vv << ",";
  return os << "]";
}
template <class T>
ostream &operator<<(ostream &os, vector<T> V) {
  os << "[";
  for (auto vv : V) os << vv << ",";
  return os << "]";
}
template <class K, class X>
ostream &operator<<(ostream &os, map<K, X> V) {
  os << "[";
  for (auto vv : V) os << vv << ",";
  return os << "]";
}
void debug_out() { cerr << '\n'; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << H;
  debug_out(T...);
}
using ii = pair<long long, long long>;
using vb = vector<bool>;
using vi = vector<long long>;
using vii = vector<ii>;
using vvi = vector<vi>;
using vvii = vector<vii>;
vi a;
class segtree {
 public:
  vi lazy;
  vi tree;
  vi li;
  vi ri;
  long long alloc(long long value, long long L = -1, long long R = -1) {
    lazy.push_back(0);
    tree.push_back(value);
    li.push_back(L);
    ri.push_back(R);
    return tree.size() - 1;
  }
  void apply(long long c, long long val) {
    lazy[c] += val;
    tree[c] += val;
  }
  long long build(long long ll, long long rr) {
    if (ll == rr) {
      return alloc(a[ll]);
    }
    long long mid = (ll + rr) / 2;
    long long L = build(ll, mid);
    long long R = build(mid + 1, rr);
    return alloc(min(tree[L], tree[R]), L, R);
  }
  inline void push(long long c, long long ll, long long rr) {
    if (lazy[c] == 0 or ll == rr) return;
    apply(li[c], lazy[c]);
    apply(ri[c], lazy[c]);
    lazy[c] = 0;
  }
  void modify(long long c, long long ll, long long rr, long long ql,
              long long qr, long long val) {
    if (ql <= ll and rr <= qr) {
      apply(c, val);
      return;
    }
    push(c, ll, rr);
    long long mid = (ll + rr) / 2;
    if (ql <= mid) modify(li[c], ll, mid, ql, qr, val);
    if (qr > mid) modify(ri[c], mid + 1, rr, ql, qr, val);
    tree[c] = min(tree[li[c]], tree[ri[c]]);
  }
  long long get(long long c, long long ll, long long rr, long long ql,
                long long qr) {
    if (ql <= ll and rr <= qr) {
      return tree[c];
    }
    push(c, ll, rr);
    long long mid = (ll + rr) / 2;
    if (qr <= mid) return get(li[c], ll, mid, ql, qr);
    if (mid < ql) return get(ri[c], mid + 1, rr, ql, qr);
    return min(get(li[c], ll, mid, ql, qr), get(ri[c], mid + 1, rr, ql, qr));
  }
};
inline bool in(long long x, ii q) { return q.first <= x and x <= q.second; }
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n;
  cin >> n;
  long long m;
  cin >> m;
  a = vi(n, 0);
  vii q(m);
  segtree st;
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
  }
  set<pair<long long, pair<long long, bool>>> qset;
  const long long root = st.build(0, n - 1);
  for (long long i = 0; i < m; i++) {
    cin >> q[i].first >> q[i].second;
    q[i].first--;
    q[i].second--;
    qset.insert({q[i].first, {i, true}});
    st.modify(root, 0, n - 1, q[i].first, q[i].second, -1);
  }
  long long best = 0;
  long long argmax = -1;
  for (long long i = 0; i < n; i++) {
    while (not qset.empty() and i == qset.begin()->first) {
      long long index = qset.begin()->second.first;
      bool remove = qset.begin()->second.second;
      qset.erase(qset.begin());
      if (remove) {
        st.modify(root, 0, n - 1, q[index].first, q[index].second, +1);
        qset.insert({q[index].second + 1, {index, false}});
      } else {
        st.modify(root, 0, n - 1, q[index].first, q[index].second, -1);
      }
    }
    long long res = a[i] - st.get(root, 0, n - 1, 0, n - 1);
    if (res > best) {
      argmax = i;
      best = res;
    }
  }
  cout << best << '\n';
  vi apply;
  for (long long i = 0; i < m; i++) {
    if (not in(argmax, q[i])) {
      apply.push_back(i + 1);
    }
  }
  cout << apply.size() << '\n';
  for (long long x : apply) {
    cout << x << " ";
  }
  cout << '\n';
}
