#include #include #include using namespace std; vector lis_vector(vector arr) { int N = arr.size(); vector val(N, 1 << 30); vector dp(N + 1); for (int i = 0; i < N; ++i) { *lower_bound(val.begin(), val.end(), arr[i]) = arr[i]; dp[i + 1] = lower_bound(val.begin(), val.end(), 1 << 30) - val.begin(); } return dp; } int main() { int N; cin >> N; vector A(N); for (int i = 0; i < N; ++i) { cin >> A[i]; } int ans = 0; for (int i = 0; i < 2; ++i) { vector dpl = lis_vector(A); reverse(A.begin(), A.end()); vector dpr = lis_vector(A); reverse(dpr.begin(), dpr.end()); reverse(A.begin(), A.end()); for (int j = 0; j < N; ++j) { ans = max(ans, max(dpl[j + 1], dpr[j]) - 1); A[j] *= -1; } } cout << ans << endl; return 0; }