Единственное отличие между легкой и сложной версиями — количество элементов в массиве.
Задан массив \(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, когда будете отправлять свой код.
Выходные данные
В первой строке выходных данных выведите одно целое число \(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\) было максимально возможным.
Если существует несколько возможных ответов, выведите любой.
Примечание
В первом тестовом примере полученный массив \(b\) будет равен \([0, -4, 1, 1, 2]\), таким образом ответ равен \(6\).
Во втором тестовом примере полученный массив \(b\) будет равен \([2, -3, 1, -1, 4]\), таким образом ответ равен \(7\).
В третьем тестовом примере вы не можете ничего сделать, таким образом ответ равен \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
2 -2 3 1 2
1 3
4 5
2 5
1 3
|
6
2
4 1
|
|
2
|
5 4
2 -2 3 1 4
3 5
3 4
2 4
2 5
|
7
2
3 2
|
|
3
|
1 0
1000000
|
0
0
|