Convoluted Operations
Tag(s):

## Compression, Data Structures, Easy-Medium, Fenwick Tree

Problem
Editorial
Analytics

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.

SAMPLE INPUT
7
1 9
1 1
2 2 10
1 2
2 4 5
0
2 6 5

SAMPLE OUTPUT
2
2
1

Explanation

In $3^{rd}$ operation you need to find the values present in the stack which were less than $10$ , after performing $2^{nd}$ operation. So the answer is $2$.

In $5^{th}$ operation you need to find the values present in the stack which were less than $5$ , after performing $4^{th}$ operation. So the answer is $2$.

In $7^{th}$ operation you need to find the values present in the stack which were less than $5$ , after performing $6^{th}$ operation. So the answer is $1$.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

January Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Implementation
• Data Structures > Advanced Data Structures
• Data Structures > Stacks
• Algorithms > Dynamic Programming
• Data Structures > Advanced Data Structures