SOLVE
LATER
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 ≤ 10^{6}
1 ≤ Q ≤ 10^{6}
1 ≤ A_{i},x ≤ 10^{6}
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.