Hỏi cách giải bài toán DP LIS 2 đầu

[NEZYA]

như đề bài bên trên mình có ý tưởng dùng dùng 1 deque ( mình sẽ đặt là LIS cho tiện gọi ) để lưu dãy tăng dần hiện tại ( tương tự như cách làm LIS nâng cao với chặt nhị phân ) ý tưởng của mình lần lượt là xét giá trị hiện tại nếu:

• giá trị hiện tại < LIS.back() thì push giá trị hiện tại vào cuối LIS ( LIS.push_back() )

• giá trị hiện tại > LIS.front() thì push giá trị hiện tại vào đầu LIS ( LIS.push_front() )

• nếu nằm ngoài trường hợp này mình sẽ tiến hành chặt nhị phân với auto it = lower_bound ( LIS.begin() , LIS.end(), giá trị hiện tại ) và thay thế vị trí con trỏ trả về bằng giá trị hiện tại

cuối cùng mình cout LIS.size()

dưới đây là code của mình:

#include<bits/stdc++.h>
using namespace std;
long long n;
long long inp[100005] = {} ;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for ( int i = 0 ; i < n ; i ++ ){
        cin >> inp[i];
    }
    deque < long long > LIS;
    for ( int i = 0 ; i < n ; i ++ ){
        if ( LIS.empty() || inp[i] < LIS.back() ) LIS.push_back(inp[i]);
        else if ( inp[i] > LIS.front() ) LIS.push_front(inp[i]);
        else{
            auto it = lower_bound ( LIS.begin() , LIS.end() , inp[i] );
            *it = inp[i];
        }
    }
    cout << LIS.size();
    return 0;
}

bài này mình bị WA mà không biết tại sao sai nữa, mọi người tìm được lỗi sai thì giúp mình nhé, mình là thành viên mới của web nên post này có thể còn xấu vs lại khó nhìn mong mọi người thông cảm, cảm ơn mọi người nhiều ạ