Leonardo and Scenery

All submissions for this problem are available.
Leonardo likes to visit different places and has planned to go on a vacation. He is travelling in a train. He is admiring the scenery outside the window. The scenery has a row of trees. He can currently see N trees. The height of the i^{th} tree is H_{i}. As the train moves further, he can see more trees. Once he sees a tree, he remembers it's height.
A fellow passenger wants to test Leonardo's intelligence. He gives him an integer k and asks him to find an integer L = length of the longest subsequence S of the sequence of tree heights H[1 ... k] such that the following two conditions are satisfied by S:
 S_{i} < S_{i + 1} for all i
 The last element of S must be H[k]
He asks many such queries. While Leonardo is answering these queries, the train is moving and new trees are appearing on the scenery. He must keep track of these trees too. So, there are two types of events: the passenger asking a question and a new tree becoming visible.
A sequence of integers Q is a subsequence of another sequence of integers P, if Q can be derived from P by deleting some integers from P without changing the order of the remaining integers.
Input
The first line of input consists of a singe integer N, the number of trees Leonardo can currently see. The next line contains N spaceseperated integers denoting the heights of the trees (H_{i}). The next line contains an integer E, the total number of events that occur. The next E lines describe each event (one event per line).
Each event is described by two spaceseperated integers: T and V. If T is 1, it means that the passenger asks a question and V denotes the value of k for the query (described above). If T is 2, it means that a new tree with height V has come into view.
Output
For each event of type T = 1, print the answer to the passenger's query (the value of L) in a singe line.
Constraints
 1 ≤ N ≤ 100000
 1 ≤ H_{i} ≤ 100000
 1 ≤ E ≤ 200000
 T will be 1 or 2
 1 ≤ V ≤ 100000, if T = 2
 V is a valid 1based index if T = 1.
Sample test
Input
3 1 2 3 3 1 3 2 4 1 4
Output
3 4
Explanation
The answer to the first query is 3 because the subsequence 1, 2, 3 satisfies all required conditions. Next, a tree of height 4 becomes visible. The answer to the second Type 1 query is 4. (Subsequence: 1, 2, 3, 4)
Author:  code_overlord 
Tags  code_overlord 
Date Added:  31102014 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions