#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + ;

const int MOD = 1e9 + ;

int i,n,ans,len;

int a[MAXN],num[MAXN],rk[MAXN],pre[MAXN],val[MAXN];

class BinaryIndexedTree

{

    private :

        int c[MAXN];

    public :

        inline int lowbit(int x)

        {

            return x & (-x);

        }

        inline void modify(int pos,int val)

        {

            int i;

            for (i = pos; i <= n; i += lowbit(i)) c[i] = (c[i] + val) % MOD;

        }

        inline int query(int pos)

        {

            int i,ans = ;

            for (i = pos; i; i -= lowbit(i)) ans = (ans + c[i]) % MOD;

            return ans;

        }

} BIT;

template <typename T> inline void read(T &x)

{

    int f = ; x = ;

    char c = getchar();

    for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; }

    for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';

    x *= f;

}

template <typename T> inline void write(T x)

{

    if (x < )

    {

        putchar('-');

        x = -x;

    }

    if (x > ) write(x/);

    putchar(x%+'');

}

template <typename T> inline void writeln(T x)

{

    write(x);

    puts("");

}

int main()

{

    read(n);

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

    {

        read(a[i]);

        num[i] = a[i];

    }

    sort(num+,num+n+);

    len = unique(num+,num+n+) - num - ;

    for (i = ; i <= n; i++) rk[i] = lower_bound(num+,num+len+,a[i]) - num;

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

    {

        val[i] = BIT.query(rk[i] - ) + ;

        BIT.modify(rk[i],(val[i] - val[pre[rk[i]]] + MOD) % MOD);

        pre[rk[i]] = i;

    }

    for (i = n; i >= ; i--)

    {

        if (pre[rk[i]])

        {

            ans = (ans + val[i] - ) % MOD;

            pre[rk[i]] = ;

        }

    }

    writeln(ans);

    return ;

}