All Tracks Algorithms Searching Binary Search Problem

Monk meets Dynamic Array
Tag(s):

Binary Search, Medium

Problem
Editorial
Analytics

In order to explore new things, Monk went to see the "Algo Show", where he saw a dynamic array $$A_{1}, A_{2}...A_{N}$$. The array made the show very interesting, by processing $$Q$$ operations on itself.

The operations are of following two types:
1 X : means push element X at the back of the array.
2 : means pop the last element of the array.

Note: It is guaranteed that, no pop operation will be applied on the empty array in the given input.

In order to make the show more interactive, after preforming each operation, the array asked the length of the Longest Increasing Subsequence (LIS) of the resulting array from the audience.
Being greedy for fame in the new world, Monk wants to answer all of the questions asked by the dynamic array.
Help Monk for the same.

INPUT:
First line of input will consists two integers $$N$$ and $$Q$$. Next line will consists of $$N$$ integers denoting the initial array. Next $$Q$$ line will consists of operations described above.

OUTPUT:
After each operation, output the length of Longest increasing subsequence of the resulting array in new line.

CONSTRAINTS:
1 ≤ N ≤ 106
1 ≤ Q ≤ 106
1 ≤ Ai,x ≤ 106

SAMPLE INPUT
5 4
1 2 3 2 1
1 2 
1 3
2 
1 5
SAMPLE OUTPUT
3
3
3
4
Explanation

Initial seq: [1,2,3,2,1]
After 1st opeartion [1,2,3,2,1,2]. Length of LIS is 3.
After 2nd operation [1,2,3,2,1,2,3]. Length of LIS is 3.
After 3rd operation [1,2,3,2,1,2]. Length of LIS is 3.
After 4th operation [1,2,3,2,1,2,5]. Length of LIS is 4.

Time Limit: 2.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 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

CodeMonk (Checkpoint - II)

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications