#include <bits/stdc++.h>
using namespace std;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = vector<V<T>>;
template <typename T>
using Mi = map<long long, T>;
template <typename T>
using MMi = map<long long, Mi<T>>;
const double PI = 3.141592653589793238463;
vector<pair<long long, long long>> tree;
long long ansTree(long long a, long long b) { return min(a, b); }
void build(vector<long long> &arr, long long ind, long long l, long long r) {
  if (l == r) {
    tree[ind] = {arr[l], 0};
    return;
  }
  long long mid = (l + r) / 2;
  build(arr, ind * 2, l, mid);
  build(arr, ind * 2 + 1, mid + 1, r);
  tree[ind].first = ansTree(tree[ind * 2].first, tree[ind * 2 + 1].first);
  tree[ind].second = 0;
}
long long getMin(long long ind, long long tl, long long tr, long long l,
                 long long r) {
  if (l > r) return 0;
  if (l == tl && r == tr) return tree[ind].first + tree[ind].second;
  long long tm = (tl + tr) / 2;
  long long a = getMin(ind * 2, tl, tm, l, min(r, tm));
  long long b = getMin(ind * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
  return ansTree(a, b) + tree[ind].second;
}
void updateTree(long long ind, long long l, long long r, long long lup,
                long long rup, long long add) {
  if (l == lup && r == rup) {
    tree[ind].second += add;
    return;
  }
  long long mid = (l + r) / 2;
  if (lup <= mid) {
    updateTree(ind * 2, l, mid, lup, min(mid, rup), add);
  }
  if (rup > mid) {
    updateTree(ind * 2 + 1, mid + 1, r, max(mid + 1, lup), rup, add);
  }
  tree[ind].first = ansTree(tree[ind * 2].first + tree[ind * 2].second,
                            tree[ind * 2 + 1].first + tree[ind * 2 + 1].second);
}
void cinArr(vector<long long> &arr) {
  for (int i = 0; i < arr.size(); i++) {
    cin >> arr[i];
  }
}
int xx[4] = {1, -1, 0, 0};
int yy[4] = {0, 0, 1, -1};
class Node {
 private:
  long long value;

 public:
  long long l;
  long long r;
  long long mod = 0;
  Node *lChildren;
  Node *rChildren;
  long long getValue() { return value + mod; }
  long long getValue(long long ind) {
    if (l == r) {
      return getValue();
    }
    long long mid = (l + r) / 2;
    if (ind <= mid) {
      return lChildren->getValue(ind);
    } else {
      return rChildren->getValue(ind);
    }
  }
  long long ansNode(long long a, long long b) { return min(a, b); }
  Node(long long l, long long r, vector<long long> &arr) {
    this->l = l;
    this->r = r;
    if (l == r) {
      value = arr[l];
    } else {
      long long mid = (l + r) / 2;
      lChildren = new Node(l, mid, arr);
      rChildren = new Node(mid + 1, r, arr);
      value = ansNode(lChildren->getValue(), rChildren->getValue());
    }
  }
  void update(long long l, long long r, long long add) {
    if (l == this->l && r == this->r) {
      mod += add;
      return;
    }
    long long mid = (this->l + this->r) / 2;
    if (l <= mid) {
      lChildren->update(l, min(mid, r), add);
    }
    if (r > mid) {
      rChildren->update(max(mid + 1, l), r, add);
    }
    value = ansNode(lChildren->getValue(), rChildren->getValue());
  }
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long n, m;
  cin >> n >> m;
  vector<long long> arr(n);
  cinArr(arr);
  vector<pair<long long, long long>> otr(m);
  for (int i = 0; i < m; i++) {
    cin >> otr[i].first >> otr[i].second;
    otr[i].first--;
    otr[i].second--;
  }
  V<list<pair<long long, long long>>> in(n, list<pair<long long, long long>>());
  for (pair<long long, long long> p : otr) {
    for (int i = p.first; i <= p.second; i++) {
      in[i].push_back(p);
    }
  }
  tree = vector<pair<long long, long long>>(n * 4);
  build(arr, 1, 0, n - 1);
  for (pair<long long, long long> p : otr) {
    updateTree(1, 0, n - 1, p.first, p.second, -1);
  }
  long long ans = 0;
  long long ind = -1;
  for (int i = 0; i < n; i++) {
    for (pair<long long, long long> p : in[i]) {
      updateTree(1, 0, n - 1, p.first, p.second, 1);
    }
    long long lmin = tree[1].first + tree[1].second;
    long long lans = arr[i] - lmin;
    if (ans < lans) {
      ans = lans;
      ind = i;
    }
    for (pair<long long, long long> p : in[i]) {
      updateTree(1, 0, n - 1, p.first, p.second, -1);
    }
  }
  cout << ans << '\n';
  if (ind == -1) {
    cout << 0;
    return 0;
  }
  vector<long long> pans;
  for (int i = 0; i < otr.size(); i++) {
    pair<long long, long long> p = otr[i];
    if (p.first > ind || p.second < ind) {
      pans.push_back(i);
    }
  }
  cout << pans.size() << '\n';
  for (long long a : pans) {
    cout << a + 1 << " ";
  }
  return 0;
}
