{"problem":{"name":"Generate Arrays","description":{"content":"Takahashi has a sequence of length $N$: $A=(A _ 1,A _ 2,\\ldots,A _ N)$. $A$ is a permutation of $(1,2,\\ldots,N)$. He is going to perform $Q$ operations to create $1+Q$ sequences. **He lets $A$ be the ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":6000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc324_g"},"statements":[{"statement_type":"Markdown","content":"Takahashi has a sequence of length $N$: $A=(A _ 1,A _ 2,\\ldots,A _ N)$. $A$ is a permutation of $(1,2,\\ldots,N)$.\nHe is going to perform $Q$ operations to create $1+Q$ sequences. **He lets $A$ be the sequence numbered $0$**, and then begins the series of operations. The $i$\\-th operation $(1\\leq i\\leq Q)$ is represented by a triple of integers $(t _ i,s _ i,x _ i)$ and corresponds to the following operation (see also the explanations in Sample Input/Output).\n\n*   When $t _ i=1$, he removes the elements following the $x _ i$\\-th element from the sequence numbered $s _ i$ $(0\\leq s _ i\\lt i)$, and creates a new sequence numbered $i$ with the removed elements, keeping their order.\n*   When $t _ i=2$, he removes the elements greater than $x _ i$ from the sequence numbered $s _ i$ $(0\\leq s _ i\\lt i)$, and creates a new sequence numbered $i$ with the removed elements, keeping their order.\n\nFor a sequence $X$ of length $L$, every element of $X$ is among \"the elements following the $0$\\-th element.\" Also, for any $l$ such that $L\\leq l$, no element of $X$ is among \"the elements following the $l$\\-th element.\"\nFor $i=1,2,\\ldots,Q$, find the length of the sequence numbered $i$ **immediately after** the $i$\\-th operation.\n\n## Constraints\n\n*   $1\\leq N\\leq2\\times10^5$\n*   $1\\leq A _ i\\leq N\\ (1\\leq i\\leq N)$\n*   $A _ i\\neq A _ j\\ (1\\leq i\\lt j\\leq N)$\n*   $1\\leq Q\\leq2\\times10^5$\n*   $t _ i=1,2\\ (1\\leq i\\leq Q)$\n*   $0\\leq s _ i\\lt i\\ (1\\leq i\\leq Q)$\n*   $0\\leq x _ i\\leq N\\ (1\\leq i\\leq Q)$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$A _ 1$ $A _ 2$ $\\ldots$ $A _ N$\n$Q$\n$t _ 1$ $s _ 1$ $x _ 1$\n$t _ 2$ $s _ 2$ $x _ 2$\n$\\vdots$\n$t _ Q$ $s _ Q$ $x _ Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc324_g","tags":[],"sample_group":[["10\n1 8 7 4 5 6 3 2 9 10\n5\n2 0 4\n1 1 2\n2 0 2\n2 2 5\n1 0 1","6\n4\n2\n3\n1\n\nInitially, Takahashi has a sequence $A=(1,8,7,4,5,6,3,2,9,10)$ of length $10$. He lets $A=(1,8,7,4,5,6,3,2,9,10)$ be the sequence numbered $0$, and then begins the series of operations.\nIn the first operation, he removes elements greater than $4$ from the sequence numbered $0$, namely $8,7,5,6,9,10$, and creates a new sequence numbered $1$ with these elements. After this operation, the sequences numbered $0$ and $1$ are $(1,4,3,2)$ and $(8,7,5,6,9,10)$, respectively.\nIn the second operation, he removes the elements following the $2$\\-nd element from the sequence numbered $1$, namely $5,6,9,10$, and creates a new sequence numbered $2$ with these elements. After this operation, the sequences numbered $0$, $1$, and $2$ are $(1,4,3,2)$, $(8,7)$, and $(5,6,9,10)$, respectively.\nFor the third and subsequent operations, the sequences numbered $0,1,2,\\ldots,i$ after the $i$\\-th operation are as follows:\n\n*   $(1,2),(8,7),(5,6,9,10),(4,3)$\n*   $(1,2),(8,7),(5),(4,3),(6,9,10)$\n*   $(1),(8,7),(5),(4,3),(6,9,10),(2)$\n\nThe length of the sequence numbered $i$ after the $i$\\-th operation for $i=1,2,\\ldots,5$ is $6,4,2,3,1$. Print each of these in its own line."],["8\n6 7 8 4 5 1 3 2\n5\n2 0 0\n1 1 0\n2 2 0\n1 3 8\n2 2 3","8\n8\n8\n0\n0\n\nThe operations may create empty sequences."],["30\n20 6 13 11 29 30 9 10 16 5 8 25 1 19 12 18 7 2 4 27 3 22 23 24 28 21 14 26 15 17\n10\n1 0 22\n1 0 21\n2 0 15\n1 0 9\n1 3 6\n2 3 18\n1 6 2\n1 0 1\n2 5 20\n2 7 26","8\n1\n8\n4\n2\n5\n3\n8\n1\n1"]],"created_at":"2026-03-03 11:01:14"}}