#include <bits/stdc++.h>
using namespace std;
int main() {
  string alpha = "abcdefghijklmnopqrstuvwxyz";
  string Alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  iostream::sync_with_stdio(false);
  cin.tie(0);
  long long int N, M;
  cin >> N >> M;
  vector<long long int> mass(N), mass2(N), mass3(N);
  long long int maxs = -100000000, num2;
  for (long long int i = 0; i < N; i++) {
    cin >> mass[i];
    if (mass[i] > maxs) {
      maxs = mass[i];
      num2 = i;
    }
  }
  mass2 = mass;
  mass3 = mass;
  long long int mins = 100000000, num;
  vector<pair<long long int, long long int> > v(M);
  for (long long int i = 0; i < M; i++) {
    long long int x, y;
    cin >> x >> y;
    x -= 1;
    y -= 1;
    v[i].first = x;
    v[i].second = y;
    for (; x <= y; x++) {
      mass[x]--;
    }
  }
  for (long long int i = 0; i < N; i++) {
    if (mass[i] < mins) {
      mins = mass[i];
      num = i;
    }
  }
  vector<long long int> ans, ans2;
  for (long long int i = 0; i < M; i++) {
    if (num >= v[i].first && num <= v[i].second) {
      long long int x = v[i].first, y = v[i].second;
      ans.push_back(i + 1);
      for (; x <= y; x++) {
        mass2[x]--;
      }
    }
  }
  for (long long int i = 0; i < M; i++) {
    if (num2 < v[i].first || num2 > v[i].second) {
      long long int x = v[i].first, y = v[i].second;
      ans2.push_back(i + 1);
      for (; x <= y; x++) {
        mass3[x]--;
      }
    }
  }
  long long int maxf = -100000000, minf = 10000000;
  for (long long int i = 0; i < N; i++) {
    if (mass2[i] > maxf) {
      maxf = mass2[i];
    }
  }
  for (long long int i = 0; i < N; i++) {
    if (mass3[i] < minf) {
      minf = mass3[i];
    }
  }
  if ((maxf - mins) > (maxs - minf)) {
    cout << maxf - mins << endl;
    cout << ans.size() << endl;
    for (long long int i = 0; i < ans.size(); i++) {
      cout << ans[i] << " ";
    }
  } else {
    cout << maxs - minf << endl;
    cout << ans2.size() << endl;
    for (long long int i = 0; i < ans2.size(); i++) {
      cout << ans2[i] << " ";
    }
  }
}
