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 A1, A2, ..., AN 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 ≤ Ai ≤ 100000.

 

Example
Input:
3 
1 2 3

Output:
1

Input:
4
4 1 2 3

Output:
2


Scoring
Subtask 1 (10 points):   N = 10   
Subtask 2 (40 points):   N = 2000   
Subtask 2 (50 points):   N = 100000
def index(lis,l,r,k):
    while(r-l>1):
        m=l+(r-l)/2;
        if(lis[m]>=k):
            r=m
        else:
            l=m
    return r        
def count(lis,n):
    t=[]
    len1=1
    t+=[lis[0]]
    i=1
    while i<n:
        if(lis[i]<t[0]):
            t[0]=lis[i]
        elif(lis[i]>t[len1-1]):
            t+=[lis[i]]
            len1+=1
        else:
            t[index(t,-1,len1-1,lis[i])]=lis[i]
        i+=1    
    return len1            
def increasing(arr,n):
    a=[0]*n
    i=0
    while i<n:
        j=i-1
        maxindex='no'
        while j>=0:
            if(maxindex!='no'):
              if(arr[j]<arr[i]):
                 if(a[j]<a[maxindex]):
                    maxindex=j
            else:
                if(arr[j]<arr[i]):
                   maxindex=j
            j-=1
        if(maxindex!='no'):    
          a[i]=a[maxindex]+1
        else:
          a[i]=1
        i+=1
    return max(a)
#a=[6, 13, 10, 8, 11, 7, 3, 5, 2]#[ 2, 5, 3, 7, 11, 8, 10, 13, 6]
#a=a[::-1]
#print a
n=input()
a=[int(x) for x in raw_input().split()]
a=a[::-1]
print count(a,n)#,count(a[::-1],len(a))