CF1108E2 Array and Segments (Hard version)

给定你一个长度为 $n$ 的数组 $a$ ，再给定你 $m$ 对数字 $[l_i,r_i]$ 。你可以选择其中的几对数字作为两个端点，再将数组 $a$ 中的两个端点内的数字全部减一。（例如现有一对 $[l_i,r_i]$ 为 $[1,3]$ ，而数组 $a$ 为 ```1 2 3 4 5``` ，若使用这对 $[l_i,r_i]$ 数组就会变成 ``` 0 1 2 4 5 ```） 现在请你求出怎样使得数组 $a$ 中的最大值减去最小值最大。

- 第一行为 $n$ 和 $m$（$1\leq n\leq 10^5,0\leq m\leq 300$）。 - 第二行有 $n$ 个数字，表示数组 $a$（$-10^6 \leq a_i \leq 10^6$）。 - 接下来的 $m$ 行，每行有两个数字，表示一对 $[l_i,r_i]$ 。

- 第一行表示更改后的数组 $a$ 中的最大值与最小值之差； - 第二行有一个整数 $k$，表示使用了多少对 $[l_i,r_i]$ 才让数组中最大值与最小值之差最大； - 第三行有 $k$ 个整数，表示你使用了哪些 $[l_i,r_i]$ （输出其编号）。

在第一个测试用例中，可以将 $a$ 数组修改为 $[0,-4,1,1,2]$，因此答案是 $6$； 在第二个测试用例中，可以将 $a$ 数组修改为 $[2,-3,1,-1,4]$，因此答案为 $6$。 在第三个测试用例中，你无法进行修改，因此答案为 $0$。