Tree O(nlogn)

#include<stdio.h>

int main()
{
    int n;
    scanf("%d",&n);
    int arr[n+1];
    int lis[n+1];
    int ans = 1;
    for(int i = 1 ; i <= n ; i ++){
        scanf("%d",&arr[i]);
    }
    lis[1] = arr[1];
    for(int i = 2 ; i <= n ; i++){
        if(arr[i] <= lis[1]){
            lis[1] = arr[i];
        }
        else if(arr[i] > lis[ans]){
            lis[++ans] = arr[i];
        }
        else{
            int l = 1 , r = ans - 1;
            int pos = 1;
            while(l <= r){
                int m = (l+r)/2;
                if(lis[m] < arr[i]){
                    pos = m;
                    l = m + 1;
                }
                else{
                    r = m - 1;
                }
            }
            lis[pos+1] = arr[i];
        }
    }
    printf("%d",ans);
    return 0;
}