Problem Statement

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 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).

• 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.
• 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.

For 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."

For $i=1,2,\ldots,Q$, find the length of the sequence numbered $i$ immediately after the $i$-th operation.

Constraints

• $1\leq N\leq2\times10^5$
• $1\leq A _ i\leq N\ (1\leq i\leq N)$
• $A _ i\neq A _ j\ (1\leq i\lt j\leq N)$
• $1\leq Q\leq2\times10^5$
• $t _ i=1,2\ (1\leq i\leq Q)$
• $0\leq s _ i\lt i\ (1\leq i\leq Q)$
• $0\leq x _ i\leq N\ (1\leq i\leq Q)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A _ 1 A _ 2 \ldots A _ N
Q
t _ 1 s _ 1 x _ 1
t _ 2 s _ 2 x _ 2
\vdots
t _ Q s _ Q x _ Q

Output

Print $Q$ lines. The $i$-th line $(1\leq i\leq Q)$ should contain the length of the sequence numbered $i$ immediately after the $i$-th operation.