T101690 [III] No matter who will be the creator

$$\text{「嘘の嘘…それはクルリと裏返る。」}$$ $$\text{「谎言的谎言，这顷刻便能颠倒正反。」}$$

给你一个序列 $num\{\}$ 长度为 $N$，每次询问包含一个区间 $[l,r]$，查询 $$\max\{\max\limits_{l \le x < y \le r,num_x > num_y} \{num_x + num_y\},\max\limits_{i = l}^r \{num_i\}\}$$

第一行，两个正整数 $N,M$。 第二行 $N$ 个正整数 $num\{\}$，代表序列。 以下 $M$ 行每行两个正整数 $l,r$，代表询问区间 $[l,r]$。

$M$ 行，每行一个正整数代表答案。

对于 $5\%$ 的数据，$N,M \leq 5$； 对于 $30\%$ 的数据，$N,M \leq 10^3$； 对于 $60\%$ 的数据，$N,M \leq 3 \cdot 10^4$； 对于 $85\%$ 的数据，$N \leq 5 \cdot 10^4,M \leq10^5$； 对于 $100\%$ 的数据，$N \leq 10^5,M \leq 3 \cdot 10^5$。 保证数列 $num\{\}$ 随机且 $num_i \leq 10^5$。