#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <sstream>
 
using namespace std;
 
#define F(a,b) for(int a=0;a<b;++a)
typedef long long LL;
 
const int Max = 1e5 + 10;
 
LL n,ans,p[Max],s[Max];
vector<LL> lis;
 
bool cmp(LL a,LL b){ return a > b; }
void Lis(){
    int pos = 0;
    for(int i=n-1;i>=0;--i)
        if((i == n-1) || (s[i] < lis.back())){
            lis.push_back(s[i]);
            p[i] = (++pos);
        }
        else{
            vector<LL>::iterator l = lower_bound(lis.begin(),lis.end(),s[i],cmp);
            *l = s[i];
            p[i] = l - lis.begin() + 1;
        }
    F(i,n) if(p[i] == pos){
        ans += i+1;
        pos --;
    }
}
 
int main(){
    scanf("%lld",&n);
    F(i,n) scanf("%lld",&s[i]);
    Lis();
    printf("%lld\n",ans);
}