E2. Массив и отрезки (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное отличие между легкой и сложной версиями — количество элементов в массиве.

Задан массив $$$a$$$, состоящий из $$$n$$$ целых чисел. Значение $$$i$$$-го элемента массива равно $$$a_i$$$.

Также задан набор из $$$m$$$ отрезков. $$$j$$$-й отрезок равен $$$[l_j; r_j]$$$, где $$$1 \le l_j \le r_j \le n$$$.

Вы можете выбрать какое-то подмножество заданного множества отрезков и уменьшить значения элементов на каждом из выбранных отрезков на единицу (независимо). Например, если изначальный массив $$$a = [0, 0, 0, 0, 0]$$$, а заданные отрезки — $$$[1; 3]$$$ и $$$[2; 4]$$$, то вы можете выбрать оба из них и массив станет равен $$$b = [-1, -2, -2, -1, 0]$$$.

Вам необходимо выбрать какое-то подмножество заданного множества отрезков (каждый отрезок может быть выбран не более одного раза) таким образом, что если вы примените этот набор отрезков к массиву $$$a$$$ и получите массив $$$b$$$, то значение $$$\max\limits_{i=1}^{n}b_i - \min\limits_{i=1}^{n}b_i$$$ будет максимально возможным.

Заметим, что вы можете выбрать пустое множество.

Если существует несколько возможных ответов, выведите любой.

Если вы программируете на Python, рассмотрите возможность отправки решения на PyPy, а не на Python, когда будете отправлять свой код.

Входные данные

Первая строка входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 10^5, 0 \le m \le 300$$$) — длина массива $$$a$$$ и количество отрезков, соответственно.

Вторая строка входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-10^6 \le a_i \le 10^6$$$), где $$$a_i$$$ — значение $$$i$$$-го элемента массива $$$a$$$.

Следующие $$$m$$$ строк содержат по два целых числа. $$$j$$$-я из них содержит два целых числа $$$l_j$$$ и $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$), где $$$l_j$$$ и $$$r_j$$$ — концы $$$j$$$-го отрезка.

Выходные данные

В первой строке выходных данных выведите одно целое число $$$d$$$ — максимально возможное значение $$$\max\limits_{i=1}^{n}b_i - \min\limits_{i=1}^{n}b_i$$$, если $$$b$$$ — это массив, полученный применением некоторого поднабора заданных отрезков к массиву $$$a$$$.

Во второй строке выходных данных выведите одно целое число $$$q$$$ ($$$0 \le q \le m$$$) — количество отрезков, которые вы собираетесь применить.

В третьей строке выведите $$$q$$$ различных целых чисел $$$c_1, c_2, \dots, c_q$$$ в любом порядке ($$$1 \le c_k \le m$$$) — номера отрезков, которые вы собираетесь применить к массиву $$$a$$$, чтобы значение $$$\max\limits_{i=1}^{n}b_i - \min\limits_{i=1}^{n}b_i$$$ полученного массива $$$b$$$ было максимально возможным.

Если существует несколько возможных ответов, выведите любой.

Примеры
Входные данные
5 4
2 -2 3 1 2
1 3
4 5
2 5
1 3
Выходные данные
6
2
4 1
Входные данные
5 4
2 -2 3 1 4
3 5
3 4
2 4
2 5
Выходные данные
7
2
3 2
Входные данные
1 0
1000000
Выходные данные
0
0
Примечание

В первом тестовом примере полученный массив $$$b$$$ будет равен $$$[0, -4, 1, 1, 2]$$$, таким образом ответ равен $$$6$$$.

Во втором тестовом примере полученный массив $$$b$$$ будет равен $$$[2, -3, 1, -1, 4]$$$, таким образом ответ равен $$$7$$$.

В третьем тестовом примере вы не можете ничего сделать, таким образом ответ равен $$$0$$$.