#include <bits/stdc++.h>
using namespace std;
const int INFL = (int)1e9;
const long long int INFLL = (long long int)1e18;
const double INFD = numeric_limits<double>::infinity();
const double PI = 3.14159265358979323846;
bool nearlyeq(double x, double y) { return abs(x - y) < 1e-9; }
bool inrange(int x, int t) { return x >= 0 && x < t; }
long long int rndf(double x) {
  return (long long int)(x + (x >= 0 ? 0.5 : -0.5));
}
long long int floorsqrt(double x) {
  long long int m = (long long int)sqrt(x);
  return m + (m * m <= (long long int)(x) ? 0 : -1);
}
long long int ceilsqrt(double x) {
  long long int m = (long long int)sqrt(x);
  return m + ((long long int)x <= m * m ? 0 : 1);
}
long long int rnddiv(long long int a, long long int b) {
  return (a / b + (a % b * 2 >= b ? 1 : 0));
}
long long int ceildiv(long long int a, long long int b) {
  return (a / b + (a % b == 0 ? 0 : 1));
}
long long int gcd(long long int m, long long int n) {
  if (n == 0)
    return m;
  else
    return gcd(n, m % n);
}
long long int lcm(long long int m, long long int n) {
  return m * n / gcd(m, n);
}
template <class T>
class SegTree {
 protected:
  int n, N;
  int base;
  vector<T> nodes;
  int left_of(int index) {
    if (index >= base)
      return -1;
    else
      return index * 2 + 1;
  }
  int right_of(int index) {
    if (index >= base)
      return -1;
    else
      return index * 2 + 2;
  }
  int parent_of(int index) {
    if (index == 0)
      return -1;
    else
      return (index - 1) >> 1;
  }
  void add_rec(int s, int t, int l, int r, int index, int v) {
    if (s == l && t == r) {
      nodes[index] = {nodes[index].first, nodes[index].second + v};
    } else {
      int mid = (l + r) / 2;
      if (s < mid && mid < t) {
        add_rec(s, mid, l, mid, left_of(index), v);
        add_rec(mid, t, mid, r, right_of(index), v);
      } else if (s < mid) {
        add_rec(s, t, l, mid, left_of(index), v);
      } else if (mid < t) {
        add_rec(s, t, mid, r, right_of(index), v);
      }
      int index_l = left_of(index);
      int index_r = right_of(index);
      nodes[index] = {min(nodes[index_l].first + nodes[index_l].second,
                          nodes[index_r].first + nodes[index_r].second),
                      nodes[index].second};
    }
  }

 public:
  SegTree(int n, T init) {
    SegTree::n = n;
    N = (int)pow(2, ceil(log2(n)));
    base = N - 1;
    nodes = vector<T>(base + N, init);
  }
  vector<int> get_index_above(int index, bool from_base = false) {
    if (from_base) index += base;
    vector<int> ret;
    while (index >= 0) {
      ret.push_back(index);
      index = parent_of(index);
    }
    return ret;
  }
  int cover_size(int index) {
    int cnt = 1;
    while (left_of(index) != -1) {
      index = left_of(index);
      cnt *= 2;
    }
    int l = index - base;
    int r = min(l + cnt, n);
    return max(0, r - l);
  }
  void update(const vector<int> &a) {
    int index = base;
    for (int i = 0; i < (int)(a.size()); i++) {
      nodes[index] = {a[i], 0};
      index++;
    }
    for (int i = (int)(base)-1; i >= 0; i--) {
      nodes[i] = {min(nodes[left_of(i)].first, nodes[right_of(i)].first), 0};
    }
  }
  void add(int s, int t, int x) { add_rec(s, t, 0, N, 0, x); }
  int solve() { return nodes[0].first + nodes[0].second; }
};
struct pq0_t {
  int id;
  int l, r;
  bool operator<(const pq0_t &another) const { return l > another.l; }
};
struct pq1_t {
  int id;
  int l, r;
  bool operator<(const pq1_t &another) const { return r > another.r; }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ;
  int n;
  cin >> n;
  int m;
  cin >> m;
  vector<int> a(n);
  for (int i = 0; i < (int)(n); i++) cin >> a[i];
  vector<int> l(m), r(m);
  priority_queue<pq0_t> pq0;
  priority_queue<pq1_t> pq1;
  SegTree<pair<int, int> > st(n, {INT_MAX, 0});
  st.update(a);
  set<int> lst;
  for (int i = 0; i < (int)(m); i++) {
    cin >> l[i] >> r[i];
    l[i]--;
    pq0.push({i, l[i], r[i]});
    st.add(l[i], r[i], -1);
    lst.insert(i);
  }
  int ans = INT_MIN;
  set<int> ans_lst;
  for (int i = 0; i < (int)(n); i++) {
    while (pq0.size() && pq0.top().l == i) {
      pq0_t buf = pq0.top();
      pq0.pop();
      pq1.push({buf.id, buf.l, buf.r});
      st.add(buf.l, buf.r, 1);
      lst.erase(buf.id);
    }
    while (pq1.size() && pq1.top().r == i) {
      pq1_t buf = pq1.top();
      pq1.pop();
      st.add(buf.l, buf.r, -1);
      lst.insert(buf.id);
    }
    int buf = a[i] - st.solve();
    if (buf > ans) {
      ans = buf;
      ans_lst = lst;
    }
  }
  cout << ans << endl;
  cout << ans_lst.size() << endl;
  for (auto itr = ans_lst.begin(); itr != ans_lst.end(); itr++) {
    cout << *itr + 1 << " ";
  }
  cout << endl;
}
