左侧最大值小于右侧最小值，其实就是左侧的值全部小于右侧，即，我们可以在区间 \([l,r]\) 内找到一个阈值 \(x\) 和一个位置 \(i<r\)，满足 \(\forall j\in[l,i],a_j\le x\) 且 \(\forall j\in(i,r],a_j> x\)。
考虑刻画出所有 \(a_j\le i\) 的位置组成的段，则对于相邻两段 \(A,B\)，当 \(l\in[l_A,r_A],r\in(r_A,l_B)\) 时询问区间 \([l,r]\) 一定合法。由于原序列为排列，故当 \(i\to i+1\) 时只会有一段/两段被修改，将其看作二维矩形，即为 \(O(n)\) 次矩形加，每次查询就变成了单点查，离线下来扫描线即可。
时间复杂度 \(O((n+q)\log n)\)。
将条件形式化表述后拆一拆。