E-小R的min_牛客练习赛148

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给定一个长度为 $n$ 的数组 $a_1,a_2,\ldots,a_n$ ，定义 $f(l,r)=\min\limits_{l\le i\le r}a_i$ 。
$\hspace{15pt}$ 给出 $m$ 次询问，对于每次询问，给出 $L$ 和 $R$ ，求解使得下式最小的整数 $x$ ：

$S(x)=\sum\limits_{L\le l\le r\le R}\Big\lvert f(l,r)-x\Big\rvert$

$\hspace{15pt}$ 如果存在多个 $x$ 满足条件，任意输出一个即可。

输入描述:

第一行输入两个整数 ，表示数组长度、询问次数。
第二行输入  个整数 ，表示数组中的元素。
此后  行，第  行输入两个整数 ，表示第  次询问的区间。

输出描述:

输对于每一次询问，新起一行输出一个整数 ，表示使得  最小的 。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

示例1

输入

复制

输出

复制

2
2

说明

注意，答案不唯一，对于第一次询问，输出  也是正确的。