#include #include #include using namespace std; const int BUF = 3005; int N, A[BUF]; void read() { cin >> N; N += 2; A[0] = A[N - 1] = -1; for (int i = 1; i < N - 1; ++i) cin >> A[i]; } int rec(bool doLeft, int L, int R, int dp[2][BUF][BUF]) { if (L > R) return 0; int &ret = dp[doLeft][L][R]; if (ret != -1) return ret; ret = 0; if (doLeft) { if (A[L] > A[R]) ret = max(ret, rec(!doLeft, L, R, dp) + 1); ret = max(ret, rec(doLeft, L + 1, R, dp)); } else { if (A[L] < A[R]) ret = max(ret, rec(!doLeft, L, R, dp) + 1); ret = max(ret, rec(doLeft, L, R - 1, dp)); } return ret; } void work() { static int dp[2][BUF][BUF]; memset(dp, -1, sizeof(dp)); cout << max(rec(0, 0, N - 2, dp), rec(1, 1, N - 1, dp)) << endl; } int main() { read(); work(); return 0; }