#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
const int maxm = 310;
int n, m;
int a[maxn], l[maxm], r[maxm], ans[maxn];
vector<int> add[maxn], sub[maxn];
struct node {
  int l, r;
  int maxx, minn, lazy;
} tree[maxn << 2];
void push_up(int k) {
  tree[k].maxx = max(tree[k << 1].maxx, tree[k << 1 | 1].maxx);
  tree[k].minn = min(tree[k << 1].minn, tree[k << 1 | 1].minn);
}
void push_down(int k) {
  if (tree[k].l != tree[k].r) {
    tree[k << 1].maxx += tree[k].lazy, tree[k << 1].minn += tree[k].lazy;
    tree[k << 1 | 1].maxx += tree[k].lazy,
        tree[k << 1 | 1].minn += tree[k].lazy;
    tree[k << 1].lazy += tree[k].lazy;
    tree[k << 1 | 1].lazy += tree[k].lazy;
  }
  tree[k].lazy = 0;
}
void build(int k, int l, int r) {
  tree[k].l = l;
  tree[k].r = r;
  if (l == r) {
    tree[k].maxx = a[l];
    tree[k].minn = a[l];
    tree[k].lazy = 0;
    return;
  }
  int mid = (l + r) >> 1;
  build(k << 1, l, mid);
  build(k << 1 | 1, mid + 1, r);
  push_up(k);
}
void update(int k, int l, int r, int x) {
  if (tree[k].lazy) push_down(k);
  tree[k].maxx += x;
  tree[k].minn += x;
  if (tree[k].l == l && tree[k].r == r) {
    tree[k].lazy += x;
    return;
  }
  int mid = (tree[k].l + tree[k].r) >> 1;
  if (r <= mid)
    update(k << 1, l, r, x);
  else if (l > mid)
    update(k << 1 | 1, l, r, x);
  else {
    update(k << 1, l, mid, x);
    update(k << 1 | 1, mid + 1, r, x);
  }
  push_up(k);
}
int query_max(int k, int l, int r) {
  int maxx;
  if (tree[k].lazy) push_down(k);
  if (tree[k].l == l && tree[k].r == r) return tree[k].maxx;
  int mid = (tree[k].l + tree[k].r) >> 1;
  if (r <= mid)
    maxx = query_max(k << 1, l, r);
  else if (l > mid)
    maxx = query_max(k << 1 | 1, l, r);
  else
    maxx = max(query_max(k << 1, l, mid), query_max(k << 1 | 1, mid + 1, r));
  return maxx;
}
int query_min(int k, int l, int r) {
  int minn;
  if (tree[k].lazy) push_down(k);
  if (tree[k].l == l && tree[k].r == r) return tree[k].minn;
  int mid = (tree[k].l + tree[k].r) >> 1;
  if (r <= mid)
    minn = query_min(k << 1, l, r);
  else if (l > mid)
    minn = query_min(k << 1 | 1, l, r);
  else
    minn = min(query_min(k << 1, l, mid), query_min(k << 1 | 1, mid + 1, r));
  return minn;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &l[i], &r[i]);
    sub[l[i]].push_back(i);
    add[r[i]].push_back(i);
  }
  build(1, 1, n);
  int d = -1, p;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < add[i - 1].size(); j++) {
      int id = add[i - 1][j];
      update(1, l[id], r[id], 1);
    }
    for (int j = 0; j < sub[i].size(); j++) {
      int id = sub[i][j];
      update(1, l[id], r[id], -1);
    }
    int det = query_max(1, 1, n) - query_min(1, 1, n);
    if (det > d) {
      d = det;
      p = i;
    }
  }
  printf("%d\n", d);
  int t = 0;
  for (int i = 1; i <= m; i++) {
    if (l[i] <= p && p <= r[i]) ans[t++] = i;
  }
  printf("%d\n", t);
  for (int i = 0; i < t; i++) {
    if (i != 0) printf(" ");
    printf("%d ", ans[i]);
  }
  printf("\n");
  return 0;
}
