2160 合唱队

#include <iostream>
using namespace std;

int main()
{
    int height[1000];
    int dp[1000][1000][2] = {0};
    int N;
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> height[i];
    for (int i = N - 1; i >= 0; i--)
        for (int j = i; j < N; j++)
        {
            if (i == j)
            {
                dp[i][j][0] = 1;
                continue;
            }
            if (height[j] > height[j - 1])
                dp[i][j][1] += dp[i][j - 1][1];
            if (height[j] > height[i])
                dp[i][j][1] += dp[i][j - 1][0];
            if (height[i] < height[j])
                dp[i][j][0] += dp[i + 1][j][1];
            if (height[i] < height[i + 1])
                dp[i][j][0] += dp[i + 1][j][0];
            dp[i][j][0]%=19650827;
            dp[i][j][1]%=19650827;
        }
    cout << (dp[0][N - 1][0] + dp[0][N - 1][1])%19650827;
}