#include <stdio.h>

#define maxn 2010
#define mod 429467296LL

int n;
int a[maxn];
unsigned int c[maxn][maxn];
long long sol;

int main()
{
    freopen("psir.in","r",stdin);
    freopen("psir.out","w",stdout);
    
    int i,j,aux,k;
    
    scanf("%d ",&n);
    
    for (i=1;i<=n;i++) scanf("%d ",&a[i]);   
    
    for (i=1;i<=n;i++)
      for (j=1;j<i;j++) c[i][j]=1;
      
   for (i=1;i<=n;i++)
      for (j=1;j<i;j++)
        for (k=1;k<j;k++) 
          if (((a[k]<a[i]) && (a[i]<a[j])) || ((a[j]<a[i]) && (a[i]<a[k]))) c[i][j]=(0LL+c[i][j]+c[j][k])%mod;
          
    for (i=1;i<=n;i++)
      for (j=1;j<i;j++) sol=(0LL+sol+c[i][j])%mod;
      
    printf("%lld\n",sol);   
    
    return 0; 
}