#include <bits/stdc++.h>
using namespace std;
long long n, m;
long long a[200010];
const long long inf_int = 1e9;
pair<long long, long long> S[200010];
long long st[400010];
long long st_[400010];
long long lazy[400010];
void construct_st(int l = 1, int r = n, int i = 0) {
  if (l == r) {
    st[i] = a[l];
    st_[i] = a[l];
    return;
  }
  int mid = (l + r) >> 1;
  construct_st(l, mid, i * 2 + 1);
  construct_st(mid + 1, r, i * 2 + 2);
  st[i] = max(st[i * 2 + 1], st[i * 2 + 2]);
  st_[i] = min(st_[i * 2 + 1], st_[i * 2 + 2]);
}
void update(int s, int e, int value, int l = 1, int r = n, int i = 0) {
  if (lazy[i]) {
    st[i] += lazy[i];
    st_[i] += lazy[i];
    if (l != r) {
      lazy[i * 2 + 1] += lazy[i];
      lazy[i * 2 + 2] += lazy[i];
    }
    lazy[i] = 0;
  }
  if (e < l || s > r) return;
  if (s <= l && r <= e) {
    st[i] += value;
    st_[i] += value;
    if (l != r) {
      lazy[i * 2 + 1] += value;
      lazy[i * 2 + 2] += value;
    }
    return;
  }
  int mid = (l + r) >> 1;
  update(s, e, value, l, mid, i * 2 + 1);
  update(s, e, value, mid + 1, r, i * 2 + 2);
  st[i] = max(st[i * 2 + 1], st[i * 2 + 2]);
  st_[i] = min(st_[i * 2 + 1], st_[i * 2 + 2]);
}
int rmq(int s, int e, int l = 1, int r = n, int i = 0) {
  if (lazy[i]) {
    st[i] += lazy[i];
    st_[i] += lazy[i];
    if (l != r) {
      lazy[i * 2 + 1] += lazy[i];
      lazy[i * 2 + 2] += lazy[i];
    }
    lazy[i] = 0;
  }
  if (e < l || s > r) return inf_int;
  if (s <= l && r <= e) return st_[i];
  int mid = (l + r) >> 1;
  long long L = rmq(s, e, l, mid, i * 2 + 1);
  long long R = rmq(s, e, mid + 1, r, i * 2 + 2);
  return min(L, R);
}
int rMq(int s, int e, int l = 1, int r = n, int i = 0) {
  if (lazy[i]) {
    st[i] += lazy[i];
    st_[i] += lazy[i];
    if (l != r) {
      lazy[i * 2 + 1] += lazy[i];
      lazy[i * 2 + 2] += lazy[i];
    }
    lazy[i] = 0;
  }
  if (e < l || s > r) return -inf_int;
  if (s <= l && r <= e) return st[i];
  int mid = (l + r) >> 1;
  long long L = rMq(s, e, l, mid, i * 2 + 1);
  long long R = rMq(s, e, mid + 1, r, i * 2 + 2);
  return max(L, R);
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= m; i++) {
    cin >> S[i].first;
    cin >> S[i].second;
  }
  construct_st();
  long long maxi = rMq(1, n);
  long long mini = rmq(1, n);
  long long answer = maxi - mini;
  long long answer_index = -1;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      int L = S[j].first;
      int R = S[j].second;
      if (i < L || i > R) {
        update(L, R, -1);
      }
    }
    maxi = rMq(1, n);
    mini = rmq(1, n);
    long long possible_answer = maxi - mini;
    if (possible_answer > answer) {
      answer = possible_answer;
      answer_index = i;
    }
    for (int j = 1; j <= m; j++) {
      int L = S[j].first;
      int R = S[j].second;
      if (i < L || i > R) {
        update(L, R, 1);
      }
    }
  }
  cout << answer << "\n";
  if (answer_index != -1) {
    vector<int> changes;
    for (int j = 1; j <= m; j++) {
      int L = S[j].first;
      int R = S[j].second;
      if (answer_index < L || answer_index > R) {
        changes.push_back(j);
      }
    }
    cout << changes.size() << "\n";
    for (auto t : changes) {
      cout << t << " ";
    }
    cout << "\n";
  } else {
    cout << 0 << "\n";
  }
}
