int longestIncreasingSubsequence(vector<int> arr) {
    vector<int> length = {0, arr[0]};
    for (int i=1; i < arr.size(); i++) {
        auto L = lower_bound(length.begin()+1, length.end(), arr[i]);
        if (L != length.end()) *L = arr[i];
        else length.push_back(arr[i]);
    }
    return length.size()-1;
}