#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m;
  cin >> n >> m;
  int A[n];
  for (int i = 0; i < n; i++) cin >> A[i];
  pair<int, int> P[m];
  vector<vector<int>> L(n), R(n);
  for (int j = 0; j < m; j++) {
    cin >> P[j].first >> P[j].second;
    --P[j].first;
    --P[j].second;
    L[P[j].second].push_back(P[j].first);
    R[P[j].first].push_back(P[j].second);
  }
  vector<int> V(n, -1e9);
  int mn = A[0];
  vector<int> B(n, 0);
  for (int i = 0; i < n; i++) {
    V[i] = max(V[i], A[i] - mn);
    for (auto j : L[i])
      while (j <= i) {
        --B[j];
        mn = min(mn, A[j] + B[j]);
        ++j;
      }
    mn = min(mn, A[i] + B[i]);
  }
  mn = A[n - 1];
  B = vector<int>(n, 0);
  for (int i = n - 1; i >= 0; i--) {
    V[i] = max(V[i], A[i] - mn);
    for (auto j : R[i])
      while (j >= i) {
        --B[j];
        mn = min(mn, A[j] + B[j]);
        --j;
      }
    mn = min(mn, A[i] + B[i]);
  }
  int ans = *max_element(V.begin(), V.end());
  vector<int> res;
  for (int i = 0; i < n; i++)
    if (V[i] == ans) {
      for (int j = 0; j < m; j++)
        if (i < P[j].first || P[j].second < i) res.push_back(j);
      break;
    }
  cout << ans << endl << res.size() << endl;
  for (int i = 0; i < res.size(); i++) cout << res[i] + 1 << " ";
  return 0;
}
