#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e5 + 10 ;

int arr[MAX] , dp[MAX] ;
long long dpways[MAX] ;
int n ;

struct segment_tree
{
    vector<int>v ;
    vector<long long> tree ;
    int sz ;
    bool flag ;
    void init(vector<int>v2 , bool t)
    {
        if(t == 0)
            flag = 0 ;
        else
            flag = 1 ;
        sz = (int)v2.size() ;
        v = v2 ;
        sort(v.begin() , v.end()) ;
        tree.resize(sz*4+10) ;
        for(int i = 0 ; i <= sz*4 ; ++i)
            tree[i] = 0 ;
    }
    int getidx1(int idx)
    {
        int idx2 = lower_bound(v.begin() , v.end() , idx) - v.begin() ;
        return idx2 ;
    }
    int getidx2(int idx)
    {
        int idx2 = lower_bound(v.begin() , v.end() , idx) - v.begin() ;
        idx2-- ;
        return idx2 ;
    }
    void update(int node , int l , int r , int idx , long long v)
    {
        if(idx > r || idx < l || idx < 0)
            return ;
        if(l == r)
        {
            if(flag == 0)
                tree[node] = max(tree[node] , v) ;
            else
                tree[node] = v ;
            return ;
        }
        int mid = (l + r) >> 1 ;
        update(node << 1 , l , mid , idx , v) ;
        update(node << 1 | 1 , mid+1 , r , idx , v) ;
        if(flag == 0)
            tree[node] = max(tree[node << 1] , tree[node << 1 | 1]) ;
        else
            tree[node] = tree[node << 1] + tree[node << 1 | 1] ;
    }

    long long query(int node , int l , int r , int from , int to)
    {
        if(from > r || to < l || from > to)
            return 0 ;
        if(l >= from && r <= to)
            return tree[node] ;
        int mid = (l + r) >> 1 ;
        long long a = query(node << 1 , l , mid , from , to) ;
        long long b = query(node << 1 | 1 , mid+1 , r , from , to) ;
        if(flag == 0)
            return max(a , b) ;
        else
            return (a + b) ;
    }

    void update(int idx , long long val)
    {
        idx = getidx1(idx) ;
        update(1 , 0 , sz , idx , val) ;
    }

    int query(int idx)
    {
        idx = getidx2(idx) ;
        return query(1 , 0 , sz , 0 , idx) ;
    }
};

vector< vector<int> >LIS(MAX) ;

int main()
{
    ios_base::sync_with_stdio(0) ;
    cin.tie(0) ;
    cin>>n ;
    vector<int>v ;
    for(int i = 0 ; i < n ; ++i)
    {
        cin>>arr[i] ;
        v.push_back(arr[i]) ;
    }
    segment_tree st ;
    st.init(v , 0) ;
    int Max = 0 ;
    for(int i = 0 ; i < n ; ++i)
    {
        dp[i] = st.query(arr[i]) + 1 ;
        Max = max(Max , dp[i]) ;
        st.update(arr[i] , dp[i]) ;
        LIS[dp[i]].push_back(arr[i]) ;
    }
    vector<segment_tree>tree(n+1) ;
    for(int i = 1 ; i <= n ; ++i)
    {
        if(LIS[i].size() > 0)
            tree[i].init(LIS[i] , 1) ;
    }
    long long ans = 0ll ;
    for(int i = 0 ; i < n ; ++i)
    {
        if(dp[i] == 1)
            dpways[i] = 1ll ;
        else
            dpways[i] = tree[dp[i]-1].query(arr[i]) ;
        tree[dp[i]].update(arr[i] , dpways[i]) ;
        if(dp[i] == Max)
            ans += dpways[i] ;
    }
    return cout<<ans<<"\n" , 0 ;
}