#include <bits/stdc++.h>
using namespace std;
const long long sz = 1e5 + 5;
vector<long long> A(sz, 0), Lazy(4 * sz, 0), Tree(4 * sz, 0);
long long n, m;
void Built(long long Node, long long I, long long F) {
  if (I == F) {
    Tree[Node] = A[I];
    return;
  }
  long long M = (I + F) / 2;
  Built(2 * Node + 1, I, M);
  Built(2 * Node + 2, M + 1, F);
  Tree[Node] = max(Tree[2 * Node + 1], Tree[2 * Node + 2]);
  return;
}
void Update(long long Node, long long I, long long F, long long L, long long R,
            long long Value) {
  if (Lazy[Node] != 0) {
    Tree[Node] += (Lazy[Node]);
    Lazy[2 * Node + 1] += Lazy[Node];
    Lazy[2 * Node + 2] += Lazy[Node];
    Lazy[Node] = 0;
  }
  if (L > F || R < I) {
    return;
  }
  if (I >= L && F <= R) {
    Tree[Node] += Value;
    Lazy[2 * Node + 1] += Value;
    Lazy[2 * Node + 2] += Value;
    return;
  }
  long long M = (I + F) / 2;
  Update(2 * Node + 1, I, M, L, R, Value);
  Update(2 * Node + 2, M + 1, F, L, R, Value);
  Tree[Node] = max(Tree[2 * Node + 1], Tree[2 * Node + 2]);
  return;
}
long long Query(long long Node, long long I, long long F, long long L,
                long long R) {
  if (Lazy[Node] != 0) {
    Tree[Node] += (Lazy[Node]);
    Lazy[2 * Node + 1] += Lazy[Node];
    Lazy[2 * Node + 2] += Lazy[Node];
    Lazy[Node] = 0;
  }
  if (L > F || R < I) return INT_MIN;
  if (I >= L && F <= R) {
    return Tree[Node];
  }
  long long M = (I + F) / 2;
  return max(Query(2 * Node + 1, I, M, L, R),
             Query(2 * Node + 2, M + 1, F, L, R));
}
int main() {
  cin >> n >> m;
  long long Min = INT_MAX;
  long long Max = INT_MIN;
  long long ansIn = -1;
  for (long long i = 0; i < n; i++) {
    cin >> A[i];
    Min = min(Min, A[i]);
    Max = max(Max, A[i]);
  }
  long long ans = Max - Min;
  Built(0, 0, n - 1);
  vector<pair<long long, long long> > tmp(m);
  map<pair<long long, long long>, vector<long long> > mp;
  for (long long i = 0; i < m; i++) {
    cin >> tmp[i].first >> tmp[i].second;
    tmp[i].first = tmp[i].first - 1;
    tmp[i].second = tmp[i].second - 1;
    mp[{tmp[i].first, tmp[i].second}].push_back(i + 1);
  }
  sort(tmp.begin(), tmp.end());
  long long i = 0, j = 0;
  multiset<pair<long long, long long> > Set;
  for (long long k = 0; k < n; k++) {
    while (!Set.empty()) {
      auto it = Set.begin();
      auto p = *it;
      if (p.first < k) {
        Update(0, 0, n - 1, p.second, p.first, 1);
        Set.erase(it);
      } else
        break;
    }
    while (j < m && tmp[j].first <= k && tmp[j].second >= k) {
      Update(0, 0, n - 1, tmp[j].first, tmp[j].second, -1);
      Set.insert({tmp[j].second, tmp[j].first});
      j++;
    }
    long long sze = Set.size();
    long long x = Query(0, 0, n - 1, 0, n - 1);
    long long y = A[k] - sze;
    if (ans < x - y) {
      ans = x - y;
      ansIn = k;
    }
  }
  cout << ans << endl;
  if (ansIn == -1) {
    cout << 0;
    return 0;
  }
  vector<long long> Ans;
  for (long long i = 0; i < m; i++) {
    if (tmp[i].first <= ansIn && tmp[i].second >= ansIn) {
      Ans.push_back(mp[{tmp[i].first, tmp[i].second}]
                      [mp[{tmp[i].first, tmp[i].second}].size() - 1]);
      mp[{tmp[i].first, tmp[i].second}].pop_back();
    }
  }
  cout << Ans.size() << endl;
  for (auto i : Ans) cout << i << " ";
  return 0;
}
