AT_abc237_g [ABC237G] Range Sort Query

给定一个由 $1,2,\ldots,N$ 组成的长度为 $N$ 的排列 $P=(P_1,P_2,\ldots,P_N)$，以及一个整数 $X$。 此外，还给定 $Q$ 个查询。第 $i$ 个查询由三个整数 $(C_i,L_i,R_i)$ 组成。对于每个查询，对排列 $P$ 执行如下操作： - 当 $C_i=1$ 时：将 $P_{L_i},P_{L_i+1},\ldots,P_{R_i}$ 按升序排序。 - 当 $C_i=2$ 时：将 $P_{L_i},P_{L_i+1},\ldots,P_{R_i}$ 按降序排序。 按顺序依次处理所有查询后，请输出最终排列中满足 $P_i=X$ 的 $i$。

输入以如下格式从标准输入读入。 > $N$ $Q$ $X$ > $P_1$ $P_2$ $\ldots$ $P_N$ > $C_1$ $L_1$ $R_1$ > $C_2$ $L_2$ $R_2$ > $\vdots$ > $C_Q$ $L_Q$ $R_Q$

请输出答案。

### 限制条件 - $1\leq N\leq 2\times 10^5$ - $1\leq Q\leq 2\times 10^5$ - $1\leq X\leq N$ - $(P_1,P_2,\ldots,P_N)$ 是 $1,2,\ldots,N$ 的一个排列。 - $1\leq C_i\leq 2$ - $1\leq L_i\leq R_i\leq N$ - 输入均为整数。 ### 样例解释 1 最初，排列为 $P=[1,4,5,2,3]$。经过查询后变化如下： - 第 $1$ 次查询，将第 $3$ 到第 $5$ 个元素升序排序。排列变为 $P=[1,4,2,3,5]$。 - 第 $2$ 次查询，将第 $1$ 到第 $3$ 个元素降序排序。排列变为 $P=[4,2,1,3,5]$。 最终排列中 $P_3=1$，因此输出 $3$。 ### 样例解释 2 最终排列为 $P=[1,2,6,5,7,4,3]$。 由 ChatGPT 4.1 翻译