#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const double pi = acos(-1.0);
const long long INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int maxn = 305;
long long lazy[maxn * 4], mmax[maxn * 4];
int a[maxn + 5];
void push_up(int rt) { mmax[rt] = min(mmax[rt * 2], mmax[rt * 2 + 1]); }
void build(int l, int r, int rt) {
  if (l == r) {
    mmax[rt] = a[l];
    return;
  }
  int m = l + (r - l) / 2;
  build(l, m, rt << 1);
  build(m + 1, r, rt << 1 | 1);
  push_up(rt);
}
void push_down(int rt, int ln, int rn) {
  if (lazy[rt]) {
    lazy[rt * 2] += lazy[rt];
    lazy[rt * 2 + 1] += lazy[rt];
    mmax[rt * 2] += lazy[rt];
    mmax[rt * 2 + 1] += lazy[rt];
    lazy[rt] = 0;
  }
}
void update(int L, int R, int x, int l, int r, int rt) {
  if (L <= l && r <= R) {
    mmax[rt] += x;
    lazy[rt] += x;
    return;
  }
  int m = l + (r - l) / 2;
  push_down(rt, m - l + 1, r - m);
  if (L <= m) update(L, R, x, l, m, rt << 1);
  if (R > m) update(L, R, x, m + 1, r, rt << 1 | 1);
  push_up(rt);
}
long long query(int L, int R, int l, int r, int rt) {
  if (L <= l && r <= R) {
    return mmax[rt];
  }
  int m = l + (r - l) / 2;
  push_down(rt, m - l + 1, r - m);
  long long ans = inf;
  if (L <= m) ans = min(ans, query(L, R, l, m, rt << 1));
  if (R > m) ans = min(ans, query(L, R, m + 1, r, rt << 1 | 1));
  return ans;
}
int n;
int b[maxn][2];
void clear() {}
void solve() {
  clear();
  int m;
  cin >> m;
  for (int i = 1; i < n + 1; i++) cin >> a[i];
  for (int i = 1; i < m + 1; i++) {
    cin >> b[i][0] >> b[i][1];
  }
  int ans = 0;
  int inx;
  for (int i = 1; i < n + 1; i++) {
    build(1, n, 1);
    memset(lazy, 0, sizeof(lazy));
    for (int j = 1; j < m + 1; j++) {
      if (i >= b[j][0] && i <= b[j][1]) continue;
      update(b[j][0], b[j][1], -1, 1, n, 1);
    }
    int m = query(1, n, 1, n, 1);
    if (a[i] - m > ans) {
      ans = a[i] - m;
      inx = i;
    }
  }
  cout << (ans);
  cout << '\n';
  vector<int> res;
  for (int j = 1; j < m + 1; j++) {
    if (inx >= b[j][0] && inx <= b[j][1]) continue;
    res.push_back(j);
  }
  cout << (res.size());
  cout << '\n';
  for (auto it : res) {
    cout << (it);
    cout << " ";
    ;
  }
  cout << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  while (cin >> n) {
    solve();
  }
  return 0;
}
