众所周知，long_hao 擅长线段树，尤其擅长线段树3，这道题也和线段树有这浓厚的关系。
现有一个长度为 n 的序列 a_n ，和 q 个查询 [l_i, r_i] ，对于每个查询，输出区间 [l_i, r_i] 内的最大子段和。
[l, r] 最大子段和的定义为：
\max_{i = l}^{r}\max_{j = i}^{r}{\sum_{t = i}^{j}{a_t}}
第一行两个整数 n， q ， 。
第二行 n 个整数 a_i 。
接下来 q 行，每行两个整数 l_i, r_i ，表示一组询问，保证 l_i \le r_i 。
q 行，每行一个整数，表示最大子段和。
10 5 -1 -3 -2 3 -5 -8 -5 3 -12 12 1 2 3 7 7 7 1 4 6 7
-1 3 -5 3 -5
对于 100 \% 的数据，满足 n \le 200000, q \le 2000000, |a_i| \le 10 ^ 9 。