CF1108E1.Array and Segments (Easy version)

The only difference between easy and hard versions is a number of elements in the array.

You are given an array $a$ consisting of $n$ integers. The value of the $i$-th element of the array is $a_i$.

You are also given a set of $m$ segments. The $j$-th segment is $[l_j; r_j]$, where $1 \le l_j \le r_j \le n$.

You can choose some subset of the given set of segments and decrease values on each of the chosen segments by one (independently). For example, if the initial array $a = [0, 0, 0, 0, 0]$ and the given segments are $[1; 3]$ and $[2; 4]$ then you can choose both of them and the array will become $b = [-1, -2, -2, -1, 0]$.

You have to choose some subset of the given segments (each segment can be chosen at most once) in such a way that if you apply this subset of segments to the array $a$ and obtain the array $b$ then the value $\max\limits_{i=1}^{n}b_i - \min\limits_{i=1}^{n}b_i$ will be maximum possible.

Note that you can choose the empty set.

If there are multiple answers, you can print any.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.

简单版本与困难版本的唯一区别在于数组中元素的个数。

给你一个由 $n$ 个整数组成的数组 $a$，其中第 $i$ 个元素的值为 $a_i$。

你还给定一个包含 $m$ 个区间的集合。第 $j$ 个区间为 $[l_j; r_j]$，满足 $1 \le l_j \le r_j \le n$。

你可以选择该区间集合的一个子集，并对所选每个区间内的所有位置上的值独立地减 $1$。例如，若初始数组为 $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。

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.

输入的第一行包含两个整数 $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$），分别表示第 $j$ 个区间的左右端点。

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.

在输出的第一行，打印一个整数 $d$ —— 即当数组 $b$ 是通过对数组 $a$ 应用给定区间的某个子集后所得时，$\max\limits_{i=1}^{n}b_i - \min\limits_{i=1}^{n}b_i$ 的最大可能值。

在输出的第二行，打印一个整数 $q$（$0 \le q \le m$）—— 即你所应用的区间的数量。

在输出的第三行，以任意顺序打印 $q$ 个互不相同的整数 $c_1, c_2, \dots, c_q$（$1 \le c_k \le m$）—— 即你应用于数组 $a$ 的那些区间的下标，使得所得数组 $b$ 满足 $\max\limits_{i=1}^{n}b_i - \min\limits_{i=1}^{n}b_i$ 达到最大可能值。

若存在多个答案，输出任意一个即可。

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$.

在第一个例子中，得到的数组 $b$ 为 $[0, -4, 1, 1, 2]$，因此答案是 $6$。

在第二个例子中，得到的数组 $b$ 为 $[2, -3, 1, -1, 4]$，因此答案是 $7$。

在第三个例子中，你无法进行任何操作，因此答案是 $0$。