记录编号	149941	评测结果	AAAAAAAAAA
题目名称	[HNOI 2010] 合唱队	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.080 s
提交时间	2015-02-27 08:55:55	内存使用	8.08 MiB

/****************************************\
* Author : ztx
* Title  : [bzoj] 1996: [Hnoi2010]chorus 合唱队
* ALG    : dp
* CMT    :
* Time   :
\****************************************/

#include <cstdio>

int CH , NEG ;
inline void read(int& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}

inline void reads(int& ret) {
	while (ret=getchar() , ret<'!') ;
	while (CH=getchar() , CH>'!') ;
}

#define  maxn   1010LL
#define  ansmod 19650827LL

int n ;
int h[maxn] = {0} ;
int f[maxn][maxn][2] = {0} ;

int main() {
int i , d , L , R ;
	#define READ
	#ifdef  READ
		freopen("chorusu.in" ,"r",stdin ) ;
		freopen("chorusu.out","w",stdout) ;
	#endif
	read(n) ;
	for (i = 1 ; i <= n ; i ++ )
		read(h[i]) , f[i][i][0] = 1 ;
	for (d = 2 ; d <= n ; d ++ )
		for (R = d ; R <= n ; R ++ ) {
			L = R-d+1 ;
			if (h[L] < h[L+1])
				f[L][R][0] += f[L+1][R][0] ,
				f[L][R][0] %= ansmod ;
			if (h[L] < h[R])
				f[L][R][0] += f[L+1][R][1] ,
				f[L][R][0] %= ansmod ;
			if (h[R] > h[L])
				f[L][R][1] += f[L][R-1][0] ,
				f[L][R][1] %= ansmod ;
			if (h[R] > h[R-1])
				f[L][R][1] += f[L][R-1][1] ,
				f[L][R][1] %= ansmod ;
		}
	printf("%d\n", (f[1][n][0]+f[1][n][1])%ansmod) ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}