#include <bits/stdc++.h>
using namespace std;
struct node {
  long long l, r;
  long long mn, mx, add;
  node() {
    l = r = -1;
    mn = 1e18, mx = -1e18, add = 0;
  }
};
vector<long long> a;
vector<node> tree;
void build(long long i, long long l, long long r) {
  if (l > r) return;
  tree[i].l = l, tree[i].r = r;
  if (l == r) {
    tree[i].mn = a[l];
    tree[i].mx = a[l];
    return;
  }
  long long mid = (l + r) / 2;
  build(2 * i + 1, l, mid);
  build(2 * i + 2, mid + 1, r);
  tree[i].mn = min(tree[2 * i + 1].mn, tree[2 * i + 2].mn);
  tree[i].mx = max(tree[2 * i + 1].mx, tree[2 * i + 2].mx);
}
void push(long long i) {
  if (tree[i].l != tree[i].r) {
    tree[2 * i + 1].mn += tree[i].add;
    tree[2 * i + 1].mx += tree[i].add;
    tree[2 * i + 1].add += tree[i].add;
    tree[2 * i + 2].mn += tree[i].add;
    tree[2 * i + 2].mx += tree[i].add;
    tree[2 * i + 2].add += tree[i].add;
    tree[i].add = 0;
  }
}
void update(long long i, long long l, long long r, long long add) {
  push(i);
  if (l > tree[i].r || r < tree[i].l) return;
  if (tree[i].l >= l && tree[i].r <= r) {
    tree[i].mn += add;
    tree[i].mx += add;
    tree[i].add += add;
    return;
  }
  update(2 * i + 1, l, r, add);
  update(2 * i + 2, l, r, add);
  tree[i].mn = min(tree[2 * i + 1].mn, tree[2 * i + 2].mn);
  tree[i].mx = max(tree[2 * i + 1].mx, tree[2 * i + 2].mx);
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cout << fixed << setprecision(20);
  long long n, m;
  cin >> n >> m;
  a.resize(n);
  tree.resize(4 * n);
  for (auto& i : a) cin >> i;
  build(0, 0, n - 1);
  vector<pair<long long, long long> > q(m);
  for (auto& i : q) {
    cin >> i.first >> i.second;
    --i.first, --i.second;
  }
  long long ans = -1e18;
  vector<long long> res;
  for (long long i = 0; i < n; ++i) {
    vector<long long> temp;
    for (long long j = 0; j < m; ++j) {
      if (i >= q[j].first && i <= q[j].second) continue;
      update(0, q[j].first, q[j].second, -1);
      temp.push_back(j);
    }
    if (tree[0].mx - tree[0].mn >= ans) {
      ans = tree[0].mx - tree[0].mn;
      res = temp;
    }
    for (auto& j : temp) {
      update(0, q[j].first, q[j].second, 1);
    }
  }
  cout << ans << endl << (long long)res.size() << endl;
  for (auto& i : res) cout << i + 1 << ' ';
}
