#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<string>

#include<iomanip>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pb push_back

#define mp make_pair

#define Maxn 50010

#define Maxm 80002

#define LL __int64

#define Abs(x) ((x)>0?(x):(-x))

#define lson(x) (x<<1)

#define rson(x) (x<<1|1)

#define inf 100000

#define lowbit(x) (x&(-x))

#define mod 1000000000

using namespace std;

LL c[Maxn][][];

int n,num[Maxn];

struct OO{

    LL val[];

};

struct PP{

    int val,i;

    int operator<(const PP &temp) const{

        return val<temp.val;

    }

}sorted[Maxn];

void update(int pos,int num,OO temp)

{

    while(pos<=n){

        c[pos][num][]+=temp.val[];

        c[pos][num][]+=temp.val[];

        c[pos][num][]+=c[pos][num][]/mod;

        c[pos][num][]%=mod;

        pos+=lowbit(pos);

    }

}

OO Sum(int pos,int num)

{

    OO sum;

    sum.val[]=sum.val[]=;

    while(pos){

        sum.val[]+=c[pos][num][];

        sum.val[]+=c[pos][num][];

        sum.val[]+=sum.val[]/mod;

        sum.val[]%=mod;

        pos-=lowbit(pos);

    }

    return sum;

}

int main()

{

    int i,j;

    //freopen("ttt.txt","r",stdin);

    while(scanf("%d",&n)!=EOF){

        memset(c,,sizeof(c));

        for(i=;i<=n;i++){

            scanf("%d",num+i);

            sorted[i].val=num[i];

            sorted[i].i=i;

        }

        sort(sorted+,sorted++n);

        int cnt=;

        for(i=;i<=n;i++){

            if(sorted[i].val!=sorted[i-].val){

                num[sorted[i].i]=++cnt;

            }

            else num[sorted[i].i]=cnt;

        }

        OO sum;

        sum.val[]=sum.val[]=;

        OO temp;

        for(i=;i<=n;i++){

            temp=Sum(num[i]-,);

            sum.val[]+=temp.val[];

            sum.val[]+=temp.val[];

            sum.val[]+=sum.val[]/mod;

            sum.val[]%=mod;

            temp.val[]=;

            temp.val[]=;

            update(num[i],,temp);

            for(j=;j>=;j--)

            update(num[i],j,Sum(num[i]-,j-));

        }

        if(sum.val[]){

            printf("%I64d",sum.val[]);

            cout<<right<<setw()<<setfill('')<<sum.val[]<<endl;

        }

        else printf("%I64d\n",sum.val[]);

    }

    return ;

}