区间排序查询

题目描述

给定 $(1,2,\ldots,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$ 中,求满足 $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$

输出格式

输出答案。

样例

5 2 1
1 4 5 2 3
1 3 5
2 1 3

3

初始排列为 $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$。

7 3 3
7 5 3 1 2 4 6
1 1 7
2 3 6
2 5 7

7

最终排列为 $P=[1,2,6,5,7,4,3]$。

数据范围

• $1 \le N \le 2\times 10^5$
• $1 \le Q \le 2\times 10^5$
• $1 \le X \le N$
• $(P_1,P_2,\ldots,P_N)$ 是 $(1,2,\ldots,N)$ 的一个排列。
• $1 \le C_i \le 2$
• $1 \le L_i \le R_i \le N$
• 输入中的所有值均为整数。