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 ith tree is Hi. 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 sub-sequence S of the sequence of tree heights H[1 ... k] such that the following two conditions are satisfied by S:
- Si < Si + 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 sub-sequence 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.
The first line of input consists of a singe integer N, the number of trees Leonardo can currently see. The next line contains N space-seperated integers denoting the heights of the trees (Hi). 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 space-seperated 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.
For each event of type T = 1, print the answer to the passenger's query (the value of L) in a singe line.
- 1 ≤ N ≤ 100000
- 1 ≤ Hi ≤ 100000
- 1 ≤ E ≤ 200000
- T will be 1 or 2
- 1 ≤ V ≤ 100000, if T = 2
- V is a valid 1-based index if T = 1.
3 1 2 3 3 1 3 2 4 1 4
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. (Sub-sequence: 1, 2, 3, 4)
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
Fetching successful submissions