#include <bits/stdc++.h>
using namespace std;
const int M = 1e9 + 7;
struct snode {
  long long val;
  long long delta;
  snode(long long x) {
    val = x;
    delta = 0;
  }
  long long getVal() { return val + delta; }
};
class streemx {
 public:
  vector<long long> L, R, A;
  vector<snode> ST;
  int n;
  streemx(vector<long long>& a) {
    A = a;
    n = a.size();
    L.resize(4 * n);
    R.resize(4 * n);
    ST = vector<snode>(4 * n, snode(-1e18));
  }
  void init(int i, int l, int r) {
    L[i] = l;
    R[i] = r;
    if (l == r) {
      ST[i] = snode(A[l]);
      return;
    }
    long long mid = (l + r) / 2;
    init(2 * i, l, mid);
    init(2 * i + 1, mid + 1, r);
    merge(i);
  }
  void propogate(int i) {
    ST[2 * i].delta += ST[i].delta;
    ST[2 * i + 1].delta += ST[i].delta;
  }
  void merge(int i) {
    ST[i].val = max(ST[2 * i].getVal(), ST[2 * i + 1].getVal());
    ST[i].delta = 0;
  }
  void update(int i, int l, int r, long long x) {
    if (R[i] < l || r < L[i]) {
      return;
    }
    if (l <= L[i] && R[i] <= r) {
      ST[i].delta += x;
      return;
    }
    propogate(i);
    update(2 * i, l, r, x);
    update(2 * i + 1, l, r, x);
    merge(i);
  }
  long long getmax(int i, int l, int r) {
    if (R[i] < l || r < L[i]) {
      return -1e18;
    }
    if (l <= L[i] && R[i] <= r) {
      return ST[i].getVal();
    }
    propogate(i);
    long long left = getmax(2 * i, l, r);
    long long right = getmax(2 * i + 1, l, r);
    merge(i);
    return max(left, right);
  }
  long long findmaxind(int i, long long x) {
    if (L[i] == R[i]) {
      return L[i];
    }
    if (getmax(2 * i, L[2 * i], R[2 * i]) == x) {
      return findmaxind(2 * i, x);
    }
    return findmaxind(2 * i + 1, x);
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m;
  cin >> n >> m;
  vector<long long> A(n);
  for (int i = 0; i < n; ++i) {
    cin >> A[i];
  }
  streemx smx(A);
  smx.init(1, 0, n - 1);
  vector<pair<int, int>> B(m);
  vector<vector<int>> sts(n + 1);
  vector<vector<int>> ens(n + 1);
  for (int i = 0; i < m; ++i) {
    cin >> B[i].first >> B[i].second;
    --B[i].first;
    --B[i].second;
    sts[B[i].first].push_back(i);
    ens[B[i].second + 1].push_back(i);
  }
  long long ans = 0;
  vector<int> ansv;
  int sub = 0;
  int ind = -1;
  for (int i = 0; i < n; ++i) {
    for (int j : ens[i]) {
      --sub;
      pair<int, int> p = B[j];
      smx.update(1, p.first, p.second, 1);
    }
    for (int j : sts[i]) {
      ++sub;
      pair<int, int> p = B[j];
      smx.update(1, p.first, p.second, -1);
    }
    long long temp = smx.getmax(1, 0, n - 1) - (A[i] - sub);
    if (temp > ans) {
      ind = i;
      ans = temp;
    }
  }
  if (ind != -1) {
    for (int j = 0; j < m; ++j) {
      if (B[j].first <= ind && ind <= B[j].second) {
        ansv.push_back(j);
      }
    }
  }
  cout << ans << "\n";
  cout << ansv.size() << "\n";
  for (int i : ansv) {
    cout << i + 1 << " ";
  }
  cout << "\n";
  return 0;
}
