ll fun(vector<ll>& arr)
{
    if (arr.size() == 0)
        return 0;
    vector<ll> new_arr;
    new_arr.pb(arr[0]);
    for (ll i = 1; i < arr.size(); i++) {

        if (arr[i] < new_arr[0]) {
            new_arr[0] = arr[i];
        } else if (arr[i] > new_arr.back()) {
            new_arr.pb(arr[i]);
        } else {
        	ll ps = lower_bound(new_arr.begin(),new_arr.end(),arr[i]) - new_arr.begin();
        	new_arr[ps] = arr[i];
        }
    }
    return sz(new_arr);
}