#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using P = pair; constexpr int INF = 1001001001; // constexpr int mod = 1000000007; constexpr int mod = 998244353; template inline bool chmax(T& x, T y){ if(x < y){ x = y; return true; } return false; } template inline bool chmin(T& x, T y){ if(x > y){ x = y; return true; } return false; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector A(N); for(int i = 0; i < N; ++i) cin >> A[i]; vector LIS(N), LIS2(N), LDS(N), LDS2(N); vector dp(N, INF), dp2(N, INF), dp3(N, INF), dp4(N, INF); for(int i = 0; i < N; ++i){ *upper_bound(begin(dp), end(dp), A[i]) = A[i]; LIS[i] = lower_bound(begin(dp), end(dp), INF) - begin(dp); *upper_bound(begin(dp3), end(dp3), -A[i]) = -A[i]; LDS[i] = lower_bound(begin(dp3), end(dp3), INF) - begin(dp3); } for(int i = N - 1; i >= 0; --i){ *upper_bound(begin(dp2), end(dp2), A[i]) = A[i]; LIS2[i] = lower_bound(begin(dp2), end(dp2), INF) - begin(dp2); *upper_bound(begin(dp4), end(dp4), -A[i]) = -A[i]; LDS2[i] = lower_bound(begin(dp4), end(dp4), INF) - begin(dp4); } // cout << "LIS\nleft\n"; // for(int i = 0; i < N; ++i) cout << LIS[i] << ' '; // cout << "\nright\n"; // for(int i = 0; i < N; ++i) cout << LIS2[i] << ' '; // cout << "\nLDS\nleft\n"; // for(int i = 0; i < N; ++i) cout << LDS[i] << ' '; // cout << "\nright\n"; // for(int i = 0; i < N; ++i) cout << LDS2[i] << ' '; // cout << '\n'; int ans = 0; for(int i = 0; i < N; ++i){ chmax(ans, max(min(LIS[i], LIS2[i]), min(LDS[i], LDS2[i])) - 1); } cout << ans << endl; return 0; }