Array and Segments (Easy version)

Description:

Input:

The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 300, 0 \le m \le 300$$$) — the length of the array $$$a$$$ and the number of segments, respectively.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^6 \le a_i \le 10^6$$$), where $$$a_i$$$ is the value of the $$$i$$$-th element of the array $$$a$$$.

The next $$$m$$$ lines are contain two integers each. The $$$j$$$-th of them contains two integers $$$l_j$$$ and $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$), where $$$l_j$$$ and $$$r_j$$$ are the ends of the $$$j$$$-th segment.

Output:

In the first line of the output print one integer $$$d$$$ — the maximum possible value $$$\max\limits_{i=1}^{n}b_i - \min\limits_{i=1}^{n}b_i$$$ if $$$b$$$ is the array obtained by applying some subset of the given segments to the array $$$a$$$.

In the second line of the output print one integer $$$q$$$ ($$$0 \le q \le m$$$) — the number of segments you apply.

In the third line print $$$q$$$ distinct integers $$$c_1, c_2, \dots, c_q$$$ in any order ($$$1 \le c_k \le m$$$) — indices of segments you apply to the array $$$a$$$ in such a way that the value $$$\max\limits_{i=1}^{n}b_i - \min\limits_{i=1}^{n}b_i$$$ of the obtained array $$$b$$$ is maximum possible.

If there are multiple answers, you can print any.

Sample Input:

5 4
2 -2 3 1 2
1 3
4 5
2 5
1 3

Sample Output:

6
2
1 4 

Sample Input:

5 4
2 -2 3 1 4
3 5
3 4
2 4
2 5

Sample Output:

7
2
3 2 

Sample Input:

1 0
1000000

Sample Output:

0
0

Note:

In the first example the obtained array $$$b$$$ will be $$$[0, -4, 1, 1, 2]$$$ so the answer is $$$6$$$.

In the second example the obtained array $$$b$$$ will be $$$[2, -3, 1, -1, 4]$$$ so the answer is $$$7$$$.

In the third example you cannot do anything so the answer is $$$0$$$.