40分TLE

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1005;
const int mod = 19650827;
int a[N];
int t[N][N][2];
int dfs(int l, int r, int flag)
{
	if(l == r and flag)return 1 % mod;
	if(l == r)return 0;
	if(t[l][r][flag])return t[l][r][flag];
	int ans = 0;
	if(not flag)
	{
		if(a[l] < a[r])ans = (ans + dfs(l + 1, r, 1)) % mod;
		if(a[l] < a[l + 1])ans = (ans + dfs(l + 1, r, 0)) % mod;
	}
	else
	{
		if(a[l] < a[r])ans = (ans + dfs(l, r - 1, 0)) % mod;
		if(a[r] > a[r - 1])ans = (ans + dfs(l, r - 1, 1)) % mod;
	}
	return t[l][r][flag] = ans;
}
signed main()
{
	int n;
	scanf("%lld", &n);
	for(int i = 1 ; i <= n ; i ++)scanf("%lld", a + i);
	printf("%lld", (dfs(1, n, 0) + dfs(1, n, 1)) % mod);
	return 0;
}