[HOJ]205 妖怪之山

#include<cstdio>
int dp[2][2][1505],a[1505],n,ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        for(int j=i-1;j>=1;j--){
            if(a[j]<a[i]){
                dp[1][0][i]++;
                dp[1][1][i]+=(dp[0][1][j]+dp[0][0][j]);
            }
            if(a[j]>a[i]){
                dp[0][0][i]++;
                dp[0][1][i]+=(dp[1][1][j]+dp[1][0][j]);
            }
            dp[1][1][i]%=12345;
            dp[0][1][i]%=12345;
        }
        ans+=dp[1][1][i]+dp[0][1][i];
        ans%=12345;
    }
    printf("%d\n",ans);
}