简单版本和困难版本之间的唯一区别是数组中的元素数量。
给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。数组中第 $$$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 300, 0 \le m \le 300$$$) — 分别是数组 $$$a$$$ 的长度和段数。
输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$-10^6 \le a_i \le 10^6$$$),其中 $$$a_i$$$ 是数组 $$$a$$$ 的第 $$$i$$$ 个元素的值。
接下来的 $$$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 -所获得的数组 $$$b$$$ 的 \min\limits_{i=1}^{n}b_i$$$ 是最大可能的。
如果有多个答案,您可以打印任何答案。
示例
输入 #1
5 4 2 -2 3 1 2 1 3 4 5 2 5 1 3
输出 #1
6 2 1 4
输入 #2
5 4 2 -2 3 1 4 3 5 3 4 2 4 2 5
输出 #2
7 2 3 2
输入 #3
1 0 1000000
输出 #3
0 0
注意
在第一个示例中,获得的数组 $$$b$$$ 将是 $$$[0, -4, 1, 1, 2]$$$,所以答案是 $$$6$$$。
在第二个示例中,获得的数组 $$$b$$$ 将是 $$$[2, -3, 1, -1, 4]$$$,因此答案是 $$$7$$$。
在第三个示例中,您无法执行任何操作,因此答案是 $$$0$$$。