#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e9 + 10;
const ll inf_ll = 1e18 + 10;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ll n, m;
  cin >> n >> m;
  vector<ll> a(n), s = {0, n}, p, l, r;
  vector<array<ll, 2>> b(m);
  for (ll i = 0; i < n; i++) cin >> a[i];
  for (ll i = 0; i < m; i++) {
    cin >> b[i][0] >> b[i][1];
    b[i][0]--, b[i][1]--;
    s.push_back(b[i][0]);
    s.push_back(b[i][1] + 1);
  }
  ll ans = 0;
  sort((s).begin(), (s).end());
  s.erase(unique((s).begin(), (s).end()), s.end());
  0;
  for (ll i = 0; i + 1 < s.size(); i++) {
    l.push_back(inf), r.push_back(-inf), p.push_back(s[i]);
    for (ll j = s[i]; j < s[i + 1]; j++)
      (l.back() = min(l.back(), a[j])), (r.back() = max(r.back(), a[j]));
    (ans = max(ans, r.back() - l.back()));
  }
  0;
  0;
  0;
  ll k = p.size();
  vector<ll> tt;
  for (ll i = 0; i < k; i++)
    for (ll j = 0; j < k; j++) {
      ll z = 0;
      vector<ll> t;
      for (ll q = 0; q < m; q++) {
        auto [x, y] = b[q];
        if (x <= p[i] && p[i] <= y && !(x <= p[j] && p[j] <= y))
          z++, t.push_back(q);
      }
      0;
      if (z + r[j] - l[i] > ans) tt = t, ans = z + r[j] - l[i];
    }
  cout << ans << "\n" << tt.size() << "\n";
  for (ll i = 0; i < tt.size(); i++) cout << tt[i] + 1 << " ";
  cout << "\n";
}
