#include <bits/stdc++.h>
using namespace std;
long long arr[200005];
long long tv[500005], tv2[500005];
long long lazy[500005];
void maketree(int v, int left, int right) {
  if (left == right) {
    tv[v] = arr[left];
    tv2[v] = arr[left];
    return;
  } else {
    int mid = (left + right) / 2;
    maketree((v * 2 + 1), left, mid);
    maketree((v * 2 + 2), mid + 1, right);
    tv[v] = min(tv[v * 2 + 1], tv[v * 2 + 2]);
    tv2[v] = max(tv2[v * 2 + 1], tv2[v * 2 + 2]);
  }
}
void update(int v, int left, int right, int l, int r, long long value) {
  if (left > right) return;
  if (lazy[v] != 0) {
    tv[v] += lazy[v];
    tv2[v] += lazy[v];
    if (right != left) {
      lazy[v * 2 + 1] += lazy[v];
      lazy[v * 2 + 2] += lazy[v];
    }
    lazy[v] = 0;
  }
  if (left > r || l > right) return;
  if (l <= left && right <= r) {
    tv[v] += value;
    tv2[v] += value;
    if (left != right) {
      lazy[v * 2 + 1] += value;
      lazy[v * 2 + 2] += value;
    }
    return;
  }
  int mid = (left + right) / 2;
  update((v * 2 + 1), left, mid, l, r, value);
  update((v * 2 + 2), mid + 1, right, l, r, value);
  tv[v] = min(tv[v * 2 + 1], tv[v * 2 + 2]);
  tv2[v] = max(tv2[v * 2 + 1], tv2[v * 2 + 2]);
}
pair<int, int> query(int v, int left, int right, int l, int r) {
  if (left > right) return {INT_MAX, INT_MIN};
  if (lazy[v] != 0) {
    tv[v] += lazy[v];
    tv2[v] += lazy[v];
    if (left != right) {
      lazy[v * 2 + 1] = lazy[v];
      lazy[v * 2 + 2] = lazy[v];
    }
    lazy[v] = 0;
  }
  if (r < left || right < l) return {INT_MAX, INT_MIN};
  if (l <= left && right <= r) return {tv[v], tv2[v]};
  int mid = (left + right) / 2;
  pair<int, int> p1 = query((v * 2 + 1), left, mid, l, r);
  pair<int, int> p2 = query((v * 2 + 2), mid + 1, right, l, r);
  return {min(p1.first, p2.first), max(p1.second, p2.second)};
}
vector<pair<int, int> > v;
vector<int> anss;
int main() {
  long long ans = 0;
  int ind = 0, n, m, x, y;
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> arr[i];
  maketree(0, 0, n - 1);
  for (int i = 0; i < m; i++) {
    cin >> x >> y;
    x--;
    y--;
    v.push_back(make_pair(x, y));
    update(0, 0, n - 1, x, y, -1);
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (v[j].first == i) update(0, 0, n - 1, v[j].first, v[j].second, 1);
    }
    pair<int, int> pp = query(0, 0, n - 1, 0, n - 1);
    if (ans < (pp.second - pp.first)) {
      ind = i;
      ans = pp.second - pp.first;
    }
    for (int j = 0; j < m; j++) {
      if (v[j].second == i) update(0, 0, n - 1, v[j].first, v[j].second, -1);
    }
  }
  cout << ans << "\n";
  for (int i = 0; i < m; i++) {
    if (v[i].first <= ind && v[i].second >= ind)
      continue;
    else
      anss.push_back(i + 1);
  }
  cout << anss.size() << "\n";
  for (auto it : anss) cout << it << " ";
}
