Московские гориллы

Обозначим за $$$pos_x$$$ индекс числа $$$x$$$ в перестановке. Подотрезки с $$$\operatorname{MEX}>1$$$ имеют вид $$$1 \le l \le pos_1 \le r \le n$$$.

Введем обозначения: $$$l_x = \min{[pos_1, pos_2, \ldots, pos_x]}$$$, $$$r_x = \max{[pos_1, pos_2, \ldots, pos_x]}$$$.

Подотрезки с $$$\operatorname{MEX}>x$$$ имеют вид $$$1 \le l \le l_x \le r_x \le r \le n$$$. Давайте определим вид подотрезков с $$$\operatorname{MEX}=x$$$.

Если $$$pos_{x + 1} < l_x$$$, тогда подотрезки с $$$\operatorname{MEX}=x+1$$$ имеют вид $$$pos_{x+1}<l \le l_x \le r_x \le r \le n$$$

Если $$$l_x \le pos_{x + 1} \le r_x$$$, тогда не существует подотрезка с $$$\operatorname{MEX}=x + 1$$$

Если $$$r_x < pos_{x+1}$$$, тогда подотрезки с $$$\operatorname{MEX}=x+1$$$ имеют вид $$$1 \le l \le l_x \le r_x \le r < pos_{x+1}$$$

Осталось всего лишь пересечь множества таких подотрезков для $$$p$$$ и $$$q$$$, что делается тривиально.