/*
        Complexitate: O(N^2)
*/

#include <cstdio>
#include <algorithm>
using namespace std;

#define NMAX 2002
#define MOD 4294967295

int N,val[NMAX];
short int ord[NMAX];
unsigned int A[NMAX][NMAX];
unsigned int B[NMAX],C[NMAX];
short int schup[NMAX],schdown[NMAX];

void read_data()
  {
   scanf("%d",&N);
   for(int i=0;i<N;i++)
      {
       scanf("%d",&val[i]);
       ord[i]=i;
      }
  }

bool cmp(short int a, short int b)
  {
   return val[a]<val[b];
  }

void solve()
  {
   int i,j,k;
   for(i=0;i<N;i++)
      {
       // init
       for(k=0;k<N;k++)
          B[k]=C[k]=A[ord[k]][i];
       for(k=1;k<N;k++)
          {
           B[k]=(unsigned int)(((long long)B[k]+(long long)B[k-1])&MOD);
          }
       for(k=N-2;k>=0;k--)
          {
           C[k]=(unsigned int)(((long long)C[k]+(long long)C[k+1])&MOD);
          }
       // solve
       for(j=0;j<=i;j++)
          A[i][j]=0;
       for(j=i+1;j<N;j++)
          if(val[i]<val[j])
            {
             k=schup[j]+1;
             if(k<N)
               A[i][j]=(unsigned int)(((long long)1+(long long)C[k])&MOD);
             else
               A[i][j]=1;
            }
          else
            if(val[i]>val[j])
              {
               k=schdown[j]-1;
               if(k>=0)
                 A[i][j]=(unsigned int)(((long long)1+(long long)B[k])&MOD);
               else
                 A[i][j]=1;
              }
            else
              A[i][j]=1;
      }
  }


int main()
{
freopen("psir.in","r",stdin);
freopen("psir.out","w",stdout);

read_data();
sort(ord,ord+N,cmp);
for(int i=0;i<N;i++)
   if(!i)
     schdown[ord[i]]=i;
   else
     if(val[ord[i]]==val[ord[i-1]])
       schdown[ord[i]]=schdown[ord[i-1]];
     else
       schdown[ord[i]]=i;
for(int i=N-1;i>=0;i--)
   if(i==N-1)
     schup[ord[i]]=i;
   else
     if(val[ord[i]]==val[ord[i+1]])
       schup[ord[i]]=schup[ord[i+1]];
     else
       schup[ord[i]]=i;
solve();

unsigned int cnt=0;
for(int i=0;i<N;i++)
   for(int j=i+1;j<N;j++)
      cnt=(unsigned int)(((long long)cnt+(long long)A[i][j])&MOD);
printf("%u\n",cnt);

return 0;
}