Mishki is quite interested in playing games, and recently she found an empty stack. Now she wants to perform 3 types of operations on the stack:
1 \(1 \; A\) : push element A in the stack.
2 0 : pop one element from stack.
3 \(2 \; K \; X\) : find how many elements were less than X present in the stack, after performing \(K^{th}\) operation on the stack.
Can you help her in performing the above operations ?
Input:
The first line contains an integer N, denoting the number of operations.
Next N line contains, any of the 3 types of operations mentioned above, where \(i^{th}\) line contains the \(i^{th}\) operation.
Output
Print the required answer for each of the \(3^{rd}\) type of operation, in new line.
Constraints:
\(1 \le N \le 5 \times 10^5\)
\(0 \le A, X \le 10^9\)
\(1 \le K \le N\)
Notes:
1) No pop operation will be given for an empty stack.
2) Let's say, you are performing \(i^{th}\) operation on the stack and it is of \(3^{rd}\) type, then the given K will always be less than i.
3) There will be at least one \(3^{rd}\) type of operation, in the input.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial