#include<stdio.h>
#define Nmax 2003

unsigned int* C[Nmax];
int* P[Nmax];
int nr[Nmax];
long long CST=(1<<31);

int main()
{
FILE *fin=fopen("psir.in","r"),
     *fout=fopen("psir.out","w");
     
int N,A[Nmax],i,j,poz,li,lf,mij,k,q;
int aux;
unsigned int uaux,nd=0;
long long sol=0;

fscanf(fin,"%d",&N);
for(i=1;i<=N;i++)
  fscanf(fin,"%d",&A[i]);
  
for(i=1;i<=N;i++)
  {
  C[i]=new unsigned int[i+5];
  P[i]=new int [i+5];               
  }
  
long long crt;
for(i=1;i<=N;i++)
  {
  nr[i]=0;
  
  for(j=1;j<i;j++)
     {
     crt=0;
     
     if(A[j]<A[i])
       {
       li=0;lf=nr[j];
       
       while(lf-li>1)
         {
         mij=(li+lf)>>1;
         
         if(P[j][mij] <= A[i])
            li=mij;
         else
            lf=mij;
         }
       
       if(li<lf && P[j][lf]>A[i])
        crt= (long long)C[j][nr[j]] + CST - (long long)C[j][lf-1];
       crt++;                        
       crt %= CST;
       
       P[i][++nr[i]]= A[j];
       C[i][nr[i]]= (unsigned int) crt;
       }
     else
     if(A[j]>A[i])
       {
       li=1;lf=nr[j]+1;
       
       while(lf-li>1)
         {
         mij=(li+lf)>>1;
         
         if(P[j][mij] < A[i])
            li=mij;
         else
            lf=mij;
         }      
         
       if(li<lf && P[j][li]<A[i])
        crt= (long long) C[j][li];
       crt++;
       crt %= CST;                        
       
       P[i][++nr[i]]= A[j];
       C[i][nr[i]]= (unsigned int) crt;
       }
     else
       nd++;
     }
  
  //sort & stuff         
  for(j=1;j<=nr[i];j++)
     {
     k=j;
     while(k/2 && P[i][k/2] < P[i][k])
        {
        uaux = C[i][k/2];
        C[i][k/2] = C[i][k];
        C[i][k] = uaux;
        
        aux = P[i][k/2];
        P[i][k/2] = P[i][k];
        P[i][k] = aux;
        
        k/=2;                       
        }                       
     }
     
  j=nr[i];
  while(j>1)
    {
    uaux = C[i][1];
    C[i][1] = C[i][j];
    C[i][j] = uaux;
        
    aux = P[i][1];
    P[i][1] = P[i][j];
    P[i][j] = aux;
    
    j--;
    
    k=1;
    while(1)
      {
      q=2*k;
      if(q>j) break;
      if(q+1<=j && P[i][q+1] > P[i][q]) q++;
      if(P[i][k] >= P[i][q]) break;
      
      uaux = C[i][k];
      C[i][k] = C[i][q];
      C[i][q] = uaux;
       
      aux = P[i][k];
      P[i][k] = P[i][q];
      P[i][q] = aux;
      
      k=q;
      }    
    }
    
  P[i][0]= -1;
  P[i][nr[i]+1]= P[i][nr[i]]+1;
  
  C[i][0]=0;
  for(j=1;j<=nr[i];j++)
     {
     crt=(long long)C[i][j-1] + (long long)C[i][j];
     crt%=CST;
     C[i][j]= (unsigned int) crt;
     }  
     
  sol+=C[i][nr[i]];
  sol%=CST;
  }
  
sol+= (long long) nd;
sol%=CST;
   
fprintf(fout,"%lld\n",sol);
fclose(fin);
fclose(fout);
return 0;
}