#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
template <class T, class V>
bool has(const T &x, V y) {
  return x.find(y) != x.end();
}
template <typename T, typename V>
string to_string(const pair<T, V> &x) {
  return "{" + to_string(x.first) + ", " + to_string(x.second) + "}";
}
void _cerr() { cerr << "]" << endl; }
template <typename T, typename... V>
void _cerr(T t, V... v) {
  cerr << to_string(t);
  if (sizeof...(v) > 0)
    cerr << ", ", _cerr(v...);
  else
    _cerr();
}
inline int nextInt() { return abs(rand() + (rand() << 15)); }
const ll MOD = 1000000007;
const double PI = acos(-1);
inline ll Pow(ll a, ll x, ll p = MOD) {
  ll r = 1;
  for (; x; x >>= 1) {
    if (x & 1) r = r * a % p;
    a = a * a % p;
  }
  return r;
}
inline ll Inv(ll a, ll p = MOD) { return Pow(a % p, p - 2, p); }
inline void Add(ll &a, ll b, ll p = MOD) { a = (a + b) % p; }
inline void Sub(ll &a, ll b, ll p = MOD) {
  a = (a - b) % p;
  if (a < 0) a += p;
}
inline void Mul(ll &a, ll b, ll p = MOD) { a = a * b % p; }
inline ll Lmul(ll a, ll b, ll p = MOD) {
  ll r = 0;
  for (; b; b >>= 1) {
    if (b & 1) r = (r + a) % p;
    a = (a + a) % p;
  }
  return r;
}
template <typename T>
inline T lcm(T a, T b) {
  return a / __gcd(a, b) * b;
}
inline void YES(bool x) { cout << (x ? "YES\n" : "NO\n"); }
inline void Yes(bool x) { cout << (x ? "Yes\n" : "No\n"); }
inline void yes(bool x) { cout << (x ? "yes\n" : "no\n"); }
template <typename T>
inline bool tomax(T &a, T b) {
  return a < b ? a = b, true : false;
}
template <typename T>
inline bool tomin(T &a, T b) {
  return a > b ? a = b, true : false;
}
inline bool bit(ll x, int i) { return (x >> i) & 1; }
inline int bits(ll x) { return __builtin_popcount(x); }
template <typename T>
inline T toggle(T &x, int i) {
  return x ^= (1ll << i);
}
const int LIN = 1e5 + 8;
int t[LIN << 2], f[LIN << 2];
int L[LIN], R[LIN];
vector<int> p[LIN], q[LIN];
int a[LIN];
pair<int, int> s[308];
void init(int k, int l, int r) {
  if (l == r) {
    t[k] = a[l];
    f[k] = 0;
    return;
  }
  int m = (l + r) >> 1;
  init(k << 1, l, m);
  init(k << 1 ^ 1, m + 1, r);
  t[k] = min(t[k << 1], t[k << 1 ^ 1]);
}
void lazy(int k, int l, int r) {
  if (f[k] != 0) {
    t[k] += f[k];
    if (l < r) {
      f[k << 1] += f[k];
      f[k << 1 ^ 1] += f[k];
    }
    f[k] = 0;
  }
}
void update(int k, int l, int r, int x, int y, int v) {
  lazy(k, l, r);
  if (l > y || r < x) return;
  if (l >= x && r <= y) {
    f[k] += v;
    lazy(k, l, r);
    return;
  }
  int m = (l + r) >> 1;
  update(k << 1, l, m, x, y, v);
  update(k << 1 ^ 1, m + 1, r, x, y, v);
  t[k] = min(t[k << 1], t[k << 1 ^ 1]);
}
int get(int k, int l, int r, int x, int y) {
  lazy(k, l, r);
  if (l > y || r < x) return MOD;
  if (l >= x && r <= y) return t[k];
  int m = (l + r) >> 1;
  return min(get(k << 1, l, m, x, y), get(k << 1 ^ 1, m + 1, r, x, y));
}
void solve(int test_number) {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= m; i++) {
    int l, r;
    cin >> l >> r;
    p[r].push_back(l);
    q[l].push_back(r);
    s[i] = {l, r};
  }
  init(1, 1, n);
  memset(f, 0, sizeof f);
  for (int i = 1; i <= n; i++) {
    L[i] = get(1, 1, n, 1, i - 1);
    for (int j : p[i]) {
      update(1, 1, n, j, i, -1);
    }
  }
  init(1, 1, n);
  memset(f, 0, sizeof f);
  for (int i = n; i >= 1; i--) {
    R[i] = get(1, 1, n, i + 1, n);
    NULL;
    for (int j : q[i]) {
      NULL;
      update(1, 1, n, i, j, -1);
    }
  }
  int res = 0;
  vector<int> use;
  for (int i = 1; i <= n; i++) {
    int calc = a[i] - min(L[i], R[i]);
    if (calc > res) {
      res = calc;
      use.clear();
      for (int j = 1; j <= m; j++) {
        if (i < s[j].first || i > s[j].second) {
          use.push_back(j);
        }
      }
    }
  }
  cout << res << endl << (int)(use).size() << endl;
  for (int i : use) cout << i << " ";
}
void solve() {
  int test = 1;
  for (int i = 1; i <= test; i++) {
    solve(i);
  }
}
int main(int argc, char *argv[]) {
  if (argc > 1) {
    freopen(".inp", "r", stdin);
    freopen(".out", "w", stdout);
  }
  ios::sync_with_stdio(false);
  srand(time(NULL));
  solve();
  return 0;
}
