#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
const long long MOD = 1e9 + 7;
inline long long add(long long a, long long b, long long m) {
  return (((a % m + b % m) % m + m) % m);
}
inline long long mul(long long a, long long b, long long m) {
  return (((a % m * b % m) % m + m) % m);
}
struct Data {
  int mn, mx;
  Data() {
    mn = 1e6 + 1;
    mx = -1e6 - 1;
  }
  Data(long long n) { mn = mx = n; }
};
struct Segtree {
  vector<Data> st;
  vector<long long> lazy;
  int lim, sz;
  Segtree(int n) {
    sz = n;
    lim = 2 * pow(2, ceil(log2(n))) + 1;
    st.assign(lim, Data(0));
    lazy.assign(lim, 0);
  }
  int leftNode(int i) { return 2 * i + 1; }
  int rightNode(int i) { return 2 * i + 2; }
  int parentNode(int i) { return ((i - 1) / 2); }
  void push(int idx, int lo, int hi) {
    if (lo <= hi && lazy[idx]) {
      long long val = lazy[idx];
      if (lo != hi) {
        lazy[leftNode(idx)] += val;
        lazy[rightNode(idx)] += val;
      }
      st[idx].mx += val;
      st[idx].mn += val;
      lazy[idx] = 0;
    }
  }
  void merge(Data &newn, Data &l, Data &r) {
    newn.mn = min(l.mn, r.mn);
    newn.mx = max(l.mx, r.mx);
  }
  Data query(int lo, int hi, int idx, int ql, int qr) {
    push(idx, lo, hi);
    if (lo > hi || ql > hi || qr < lo) return Data();
    if (ql <= lo && hi <= qr) return st[idx];
    int mid = (lo + hi) / 2;
    Data a = query(lo, mid, leftNode(idx), ql, qr);
    Data b = query(mid + 1, hi, rightNode(idx), ql, qr);
    if (qr <= mid)
      return a;
    else if (ql > mid)
      return b;
    Data newn;
    merge(newn, a, b);
    return newn;
  }
  void update(int lo, int hi, int idx, int ql, int qr, long long val) {
    push(idx, lo, hi);
    if (lo > hi || ql > hi || qr < lo) return;
    if (lo >= ql && hi <= qr) {
      lazy[idx] += val;
      push(idx, lo, hi);
      return;
    }
    int mid = (lo + hi) / 2;
    update(lo, mid, leftNode(idx), ql, qr, val);
    update(mid + 1, hi, rightNode(idx), ql, qr, val);
    merge(st[idx], st[leftNode(idx)], st[rightNode(idx)]);
  }
  void pointUpdate(int i, long long val) { update(0, sz - 1, 0, i, i, val); }
  void rangeUpdate(int i, int j, long long val) {
    update(0, sz - 1, 0, i, j, val);
  }
  Data pointQuery(int i) { return query(0, sz - 1, 0, i, i); }
  Data rangeQuery(int i, int j) { return query(0, sz - 1, 0, i, j); }
};
void solve() {
  int n, m;
  cin >> n >> m;
  vector<int> arr(n, 0);
  Segtree tree(n);
  for (int i = 0; i < n; i++) cin >> arr[i], tree.pointUpdate(i, arr[i]);
  vector<vector<int> > str(n, vector<int>()), end(n, vector<int>());
  vector<pair<int, int> > seg;
  int ans = tree.rangeQuery(0, n - 1).mx - tree.rangeQuery(0, n - 1).mn;
  for (int i = 1; i < m + 1; i++) {
    int l, r;
    cin >> l >> r;
    l--;
    r--;
    seg.push_back({l, r});
    str[l].push_back(r);
    end[r].push_back(l);
    tree.rangeUpdate(l, r, -1);
  }
  int idx = -1;
  for (int i = 0; i < n; i++) {
    for (auto itr : str[i]) tree.rangeUpdate(i, itr, 1);
    int temp = tree.rangeQuery(0, n - 1).mx - tree.rangeQuery(0, n - 1).mn;
    if (ans < temp) {
      ans = temp;
      idx = i;
    }
    for (auto itr : end[i]) tree.rangeUpdate(itr, i, -1);
  }
  cout << ans << '\n';
  if (idx == -1) {
    cout << 0 << '\n';
    return;
  }
  vector<int> aRes;
  for (int i = 0; i < m; i++) {
    auto itr = seg[i];
    if (idx >= itr.first && idx <= itr.second) continue;
    aRes.push_back(i + 1);
  }
  cout << (long long)(aRes).size() << '\n';
  for (int x : aRes) cout << x << " ";
  cout << '\n';
  return;
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0);
  int t = 1;
  for (int tc = 1; tc < t + 1; tc++) {
    solve();
  }
  return 0;
}
