{"problem":{"name":"Range Sort Query","description":{"content":"Given is a permutation $P=(P_1,P_2,\\ldots,P_N)$ of $1,2,\\ldots,N$, and an integer $X$. Additionally, $Q$ queries are given. The $i$\\-th query is represented as a triple of numbers $(C_i,L_i,R_i)$. Eac","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":8000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc237_g"},"statements":[{"statement_type":"Markdown","content":"Given is a permutation $P=(P_1,P_2,\\ldots,P_N)$ of $1,2,\\ldots,N$, and an integer $X$.\nAdditionally, $Q$ queries are given. The $i$\\-th query is represented as a triple of numbers $(C_i,L_i,R_i)$. Each query does the following operation on the permutation $P$.\n\n*   If $C_i=1$: sort $P_{L_i},P_{L_i+1},\\ldots,P_{R_i}$ in ascending order.\n*   If $C_i=2$: sort $P_{L_i},P_{L_i+1},\\ldots,P_{R_i}$ in descending order.\n\nIn the final permutation $P$ after executing all queries in the given order, find $i$ such that $P_i=X$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 2\\times 10^5$\n*   $1 \\leq Q \\leq 2\\times 10^5$\n*   $1 \\leq X \\leq N$\n*   $(P_1,P_2,\\ldots,P_N)$ is a permutation of $(1,2,\\ldots,N)$.\n*   $1 \\leq C_i \\leq 2$\n*   $1 \\leq L_i \\leq R_i \\leq N$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $Q$ $X$\n$P_1$ $P_2$ $\\ldots$ $P_N$\n$C_1$ $L_1$ $R_1$\n$C_2$ $L_2$ $R_2$\n$\\vdots$\n$C_Q$ $L_Q$ $R_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc237_g","tags":[],"sample_group":[["5 2 1\n1 4 5 2 3\n1 3 5\n2 1 3","3\n\nInitially, the permutation is $P=[1,4,5,2,3]$. The queries change it as follows.\n\n*   $1$\\-st query sorts the $3$\\-rd through $5$\\-th elements in ascending order, making $P=[1,4,2,3,5]$.\n*   $2$\\-nd query sorts the $1$\\-st through $3$\\-rd elements in descending order, making $P=[4,2,1,3,5]$.\n\nIn the final permutation, we have $P_3=1$, so $3$ should be printed."],["7 3 3\n7 5 3 1 2 4 6\n1 1 7\n2 3 6\n2 5 7","7\n\nThe final permutation is $P=[1,2,6,5,7,4,3]$."]],"created_at":"2026-03-03 11:01:13"}}