Najdłuższy Podciąg Rosnący

//
//  main.cpp
//  Najdłuższy Podciąg Rosnący
//
//  Created by Jędrzej Dudzicz on 20.08.2017.
//  Copyright © 2017 Jędrzej Dudzicz. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    int *t=new int[n+2];
    int *a=new int[n+2];
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        t[i+1]=1e9;
    }
    t[0]=0;
    int ile=0;
    for(int i=0;i<n;++i){
        int p=0,k=n+1,s1,s=0;
        while(p<=k){
            s1=(p+k)/2;
            if(t[s1]>=a[i]){
                s=s1;
                k=s1-1;
            }
            else p=s1+1;
        }
        if(ile<s)ile=s;
        t[s]=a[i];
    }
    printf("%d\n",ile);
    return 0;
}