问题 E: 海浪

https://acm.hdu.edu.cn/contest/problem?cid=1150&pid=1004 染染船长，准备出发！ 话虽然是这么说，但出发之前除了建设好整条船，还需要观察一下海面的情况，选择一个良辰吉日出海。 海面情况的一个重要指标就是海浪，尤其是其中很长的海浪。 为了能够量化这个问题，染染将本该连续的海面离散化成为了一个长度为 $ n $ 的整数高度序列 $ h_{1}, h_{2}, \cdots, h_{n} $ ，可以认为 $ h_{i} $ 表示第 $ i $ 块海面的波动高度。此时海浪可以定义为连续的海面 $ h_{l}, h_{l+1}, \cdots, h_{r} $ ，满足存在实数基准高度 $ h_{B} $ ，使得对于 $ i=l+1, l+2, \cdots, r $ 都有： $$ \left(h_{i-1}-h_{B}\right) \cdot\left(h_{i}-h_{B}\right)<0 $$ 染染现在会给出 $ q $ 次询问，每次询问给出 $ x, y $ 表示查询完全包含在连续的海面 $ h_{x}, h_{x+1}, \cdots, h_{y} $ 内的最长海浪的长度。也就是说染染要找到海浪 $ h_{l}, h_{l+1}, \cdots, h_{r} $ 使得 $ x \leq l \leq r \leq y $ 并最大化 $ r-l+1 $ 。

本题单个测试点内包含多组测试数据。 输入第一行一个正整数 $ T(1 \leq T \leq 20) $ ，表示数据组数。 每组数据第一行两个正整数 $ n, q\left(1 \leq n, q \leq 10^{5}\right) $ ，表示海面被离散化后的序列长度。 第二行 $ n $ 个正整数 $ h_{1}, h_{2}, \cdots, h_{n}\left(-10^{9} \leq h_{i} \leq 10^{9}\right) $ ，表示海面被离散化后的序列。 接下来 $ q $ 行，第 $ i $ 行包含两个正整数 $ x, y(1 \leq x \leq y \leq n) $ ，表示第 $ i $ 次询问。 保证单个测试点内每组数据中 $ n $ 的和与 $ q $ 的和不超过 $ 10^{6} $ 。

为了避免输出量过大，输出对每组数据进行压缩。 对于每组数据，假设染染第 $ i $ 次询问的答案为 $ r_{i} $ ，你只需要输出一行一个压缩后的非负整数 $ R $ ： $$ R=\left(\sum_{i=1}^{q} i \cdot r_{i}\right) \bmod \left(10^{9}+7\right) $$

第 1 次询问的答案为 3 ，对应海浪 $ h_{1}, h_{2}, h_{3} $ 即 $ -1,1,-1 $ 。 第 2 次询问的答案为 3 ，对应海浪 $ h_{5}, h_{6}, h_{7} $ 即 $ 3,7,3 $ 。 第 3 次询问的答案为 4 ，对应海浪 $ h_{1}, h_{2}, h_{3}, h_{4} $ 即 $ -1,1,-1,1 $ 。