#include <bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr int INF = 0x3f3f3f3f;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  for (int &e : a) cin >> e;
  vector<pair<int, int>> seg(m);
  vector<vector<int>> lf(n), rg(n);
  for (int i = 0; i < m; i++) {
    cin >> seg[i].first >> seg[i].second;
    seg[i].first--;
    seg[i].second--;
    lf[seg[i].second].push_back(seg[i].first);
    rg[seg[i].first].push_back(seg[i].second);
  }
  vector<int> ansv(n, -INF);
  vector<int> add(n, 0);
  int mn = a[0];
  for (int i = 0; i < n; i++) {
    ansv[i] = a[i] - mn;
    for (int l : lf[i]) {
      for (int j = l; j <= i; j++) {
        add[j]--;
        mn = min(mn, a[j] + add[j]);
      }
    }
    mn = min(mn, a[i] + add[i]);
  }
  add.assign(n, 0);
  mn = a[n - 1];
  for (int i = n - 1; i >= 0; i--) {
    ansv[i] = max(ansv[i], a[i] - mn);
    for (int r : rg[i]) {
      for (int j = i; j <= r; j++) {
        add[j]--;
        mn = min(mn, a[j] + add[j]);
      }
    }
    mn = min(mn, a[i] + add[i]);
  }
  int ans = *max_element(begin(ansv), end(ansv));
  vector<int> out;
  for (int i = 0; i < n; i++) {
    if (ansv[i] == ans) {
      for (int j = 0; j < m; j++) {
        if (!(seg[j].first <= i && i <= seg[j].second)) {
          out.push_back(j + 1);
        }
      }
      break;
    }
  }
  cout << ans << "\n" << out.size() << "\n";
  for (auto x : out) cout << x << ' ';
}
