#include <bits/stdc++.h>
const long long MOD = (long long)1e9 + 7;
const long long inf = (long long)1e17;
using namespace std;
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
inline long long binexp(long long a, long long b, long long m) {
  long long res = 1;
  a %= m;
  while (b) {
    if (b & 1) res = (res * 1ll * a) % m;
    a = (a * 1ll * a) % m;
    b >>= 1;
  }
  return res;
}
long long prefix[305], suffix[305];
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long n, m;
  cin >> n >> m;
  vector<long long> arr(n);
  vector<pair<long long, long long> > ranges(m);
  for (long long i = 0; i < n; ++i) {
    cin >> arr[i];
  }
  vector<pair<long long, long long> > v1, v2;
  for (long long i = 0; i < m; ++i) {
    cin >> ranges[i].first >> ranges[i].second;
    ranges[i].first--;
    ranges[i].second--;
    v1.push_back({ranges[i].first, i});
    v2.push_back({ranges[i].second, i});
  }
  sort(v1.begin(), v1.end());
  sort(v2.begin(), v2.end());
  prefix[0] = *min_element(arr.begin(), arr.end());
  vector<long long> temp(n);
  for (long long i = 0; i < n; ++i) {
    temp[i] = arr[i];
  }
  for (long long i = 0; i < m; ++i) {
    prefix[i + 1] = prefix[i];
    for (long long j = ranges[v2[i].second].first;
         j <= ranges[v2[i].second].second; ++j) {
      temp[j]--;
      prefix[i + 1] = min(prefix[i + 1], temp[j]);
    }
  }
  for (long long i = 0; i < n; ++i) {
    temp[i] = arr[i];
  }
  suffix[m + 1] = prefix[0];
  for (long long i = m - 1; i >= 0; --i) {
    suffix[i + 1] = suffix[i + 2];
    for (long long j = ranges[v1[i].second].first;
         j <= ranges[v1[i].second].second; ++j) {
      temp[j]--;
      suffix[i + 1] = min(suffix[i + 1], temp[j]);
    }
  }
  long long ans = 0;
  vector<long long> t;
  for (long long i = 0; i < n; ++i) {
    long long ind1 =
        upper_bound(v2.begin(), v2.end(), make_pair(i, -1ll)) - v2.begin();
    long long ind2 =
        upper_bound(v1.begin(), v1.end(), make_pair(i, m + 5)) - v1.begin() + 1;
    long long tans = max(arr[i] - suffix[ind2], arr[i] - prefix[ind1]);
    if (tans > ans) {
      ans = tans;
      vector<long long> v;
      for (long long j = 0; j < ind1; ++j) {
        v.push_back(v2[j].second);
      }
      for (long long j = ind2 - 1; j < m; ++j) {
        v.push_back(v1[j].second);
      }
      swap(v, t);
    }
  }
  cout << ans << "\n" << t.size() << "\n";
  for (auto &it : t) {
    cout << it + 1 << " ";
  }
  return 0;
}
