{"raw_statement":[{"iden":"problem statement","content":"You are given a sequence $A = (A_1, A_2, \\ldots, A_N)$ of length $N$.\nProcess $Q$ queries in the order they are given. Each query is of one of the following two types:\n\n*   Type $1$: Given in the form `1 p x`. Change the value of $A_p$ to $x$.\n*   Type $2$: Given in the form `2 l r`. print the **number of occurrences** of the second largest value in $(A_l, A_{l+1}, \\ldots, A_r)$. More precisely, print the number of integers $i$ satisfying $l \\leq i \\leq r$ such that there is exactly one distinct value greater than $A_i$ among $A_l, A_{l+1}, \\ldots, A_r$."},{"iden":"constraints","content":"*   $1 \\leq N, Q \\leq 2 \\times 10^5$\n*   $1 \\leq A_i \\leq 10^9$\n*   For type-$1$ queries, $1 \\leq p \\leq N$.\n*   For type-$1$ queries, $1 \\leq x \\leq 10^9$.\n*   For type-$2$ queries, $1 \\leq l \\leq r \\leq N$.\n*   There is at least one type-$2$ query.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $Q$\n$A_1$ $A_2$ $\\ldots$ $A_N$\n$\\text{query}_{1}$\n$\\vdots$\n$\\text{query}_{Q}$\n\nHere, $\\text{query}_{i}$ is the $i$\\-th query and given in one of the following formats:\n\n$1$ $p$ $x$\n\n$2$ $l$ $r$"},{"iden":"sample input 1","content":"5 4\n3 3 1 4 5\n2 1 3\n2 5 5\n1 3 3\n2 2 4"},{"iden":"sample output 1","content":"1\n0\n2\n\nInitially, $A = (3, 3, 1, 4, 5)$.\nFor the first query, the second largest value in $(3, 3, 1)$ is $1$, which appears once in $3, 3, 1$, so print $1$.\nFor the second query, there is no second largest value in $(5)$, so print $0$.\nThe third query makes $A = (3, 3, 3, 4, 5)$.\nFor the fourth query, the second largest value in $(3, 3, 4)$, is $3$, which appears twice in $3, 3, 4$, so print $2$."},{"iden":"sample input 2","content":"1 1\n1000000000\n2 1 1"},{"iden":"sample output 2","content":"0"},{"iden":"sample input 3","content":"8 9\n2 4 4 3 9 1 1 2\n1 5 4\n2 7 7\n2 2 6\n1 4 4\n2 2 5\n2 2 7\n1 1 1\n1 8 1\n2 1 8"},{"iden":"sample output 3","content":"0\n1\n0\n2\n4"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}