考虑用平衡树维护。对每个节点维护是否存在长为 $3$ 的上升子序列，若不存在则还要维护最小值 $mn$、最大值 $mx$、非后缀最大值的最大值 $smx$ 和非前缀最小值的最小值 $smn$。合并两个区间时，新的区间存在长为 $3$ 的上升子序列当且仅当下面至少一个条件满足：

• 左区间或右区间存在长为 $3$ 的上升子序列。
• 左区间的 $mn<$ 右区间的 $smx$。
• 左区间的 $smn<$ 右区间的 $mx$。

维护 $smn$ 和 $smx$ 的方法类似，以 $smx$ 为例，要么从子区间直接继承，要么就是右区间的 $mx$ 在左区间的前驱。由于新的区间没有长为 $3$ 的上升子序列，所以左区间的 $smn>$ 右区间的 $mx$，因此左区间所有 $<$ 右区间的 $mx$ 的数是递减的。问题变成了求左区间第一个 $<$ 右区间的 $mx$ 的数，在平衡树上二分即可。

时间复杂度 $O((n+q)\log^2 n)$。