#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);
}