Solve the programming task below in a Python markdown code block.
Read problems statements in Russian also. 
Chef plays with the sequence of N numbers. During a single move Chef is able to choose a non-decreasing subsequence of the sequence and to remove it from the sequence. Help him to remove all the numbers in the minimal number of moves. 

------ Input ------ 

The first line of each test case contains a single N denoting the number of integers in the given sequence. The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N} denoting the given sequence

------ Output ------ 

Output a single line containing the minimal number of moves required to remove all the numbers from the sequence.

------ Constraints ------ 

$1 ≤ N ≤ 100000.$
$1 ≤ A_{i} ≤ 100000.$
 
------ Scoring ------ 

Subtask 1 (10 points):   N = 10   

Subtask 2 (40 points):   N = 2000   

Subtask 2 (50 points):   N = 100000   

----- Sample Input 1 ------ 
3 
1 2 3
----- Sample Output 1 ------ 
1
----- explanation 1 ------ 

----- Sample Input 2 ------ 
4
4 1 2 3
----- Sample Output 2 ------ 
2
----- explanation 2 ------