1 #include <set>  2 #include <map>  3 #include <cmath>  4 #include <ctime>  5 #include <queue>  6 #include <stack>  7 #include <cstdio>  8 #include <string>  9 #include <vector> 10 #include <cstdlib> 11 #include <cstring> 12 #include <iostream> 13 #include <algorithm> 14 using namespace std; 15 typedef unsigned long long ull; 16 typedef long long ll; 17 const int inf = 0x3f3f3f3f; 18 const double eps = 1e-8; 19 const int maxn = 1e5+10; 20 int seg[maxn<<2],pt[maxn<<2],a[maxn],vec[maxn],idx,n; 21 int pos1[maxn],pos2[maxn]; 22 void hash_() 23 { 24     sort(vec,vec+idx); 25     idx = unique(vec,vec+idx) - vec; 26     for (int i = 0; i < n ;i++) 27         a[i] = lower_bound(vec,vec+idx,a[i]) - vec + 1; 28 } 29 int ans,pp; 30 /* 31 void update(int l,int r,int pos,int x,int val,int s) 32 { 33     if (l == r) 34     { 35         if (val == seg[pos] && s > pt[pos]) 36             pt[pos] = s; 37         if (val > seg[pos]) 38         { 39             pt[pos] = s; 40             seg[pos] = val; 41         } 42         return ; 43     } 44     int mid = (l + r) >> 1; 45     if (x <= mid) 46         update(l,mid,pos<<1,x,val,s); 47     else 48         update(mid+1,r,pos<<1|1,x,val,s); 49     seg[pos] = max(seg[pos<<1],seg[pos<<1|1]); 50     if (seg[pos<<1] > seg[pos<<1|1]) 51         pt[pos] =pt[pos<<1]; 52     if (seg[pos<<1] < seg[pos<<1|1]) 53         pt[pos] = pt[pos<<1|1]; 54     if (seg[pos<<1] == seg[pos<<1|1]) 55         pt[pos] = max(pt[pos<<1],pt[pos<<1|1]); 56 } 57 void query(int l,int r,int pos,int ua,int ub) 58 { 59     if (ub < ua) 60         return ; 61     if (ua <= l && ub >= r) 62     { 63         if (ans < seg[pos]) 64         { 65             ans = seg[pos]; 66             pp = pt[pos]; 67         } 68         if (ans == seg[pos] && pp < pt[pos]) 69             pp = pt[pos]; 70         return ; 71     } 72     int mid = (l + r) >> 1; 73     if (ua <= mid) 74         query(l,mid,pos<<1,ua,ub); 75     if (ub > mid) 76         query(mid+1,r,pos<<1|1,ua,ub); 77 }*/ 78 inline int lowbit (int x) 79 { 80     return x & -x; 81 } 82 int c[2][maxn]; 83 void add(int x,int d,int s) 84 { 85     while (x <= idx) 86     { 87         if (c[0][x] < d) 88         { 89             c[0][x] = d; 90             c[1][x] = s; 91         } 92         if (c[0][x] == d && c[1][x] < s) 93         { 94             c[1][x] = s; 95         } 96         x += lowbit(x); 97     } 98 } 99 void query(int x)100 {101     while (x)102     {103         if (ans < c[0][x])104         {105             pp = c[1][x];106             ans = c[0][x];107         }108         if (ans == c[0][x] && pp < c[1][x])109         {110             pp = c[1][x];111         }112         x -= lowbit(x);113     }114 }115 int dp[maxn];116 int main(void)117 {118     #ifndef ONLINE_JUDGE119         freopen("in.txt","r",stdin);120     #endif121     while (~scanf ("%d",&n))122     {123         //memset(seg,0,sizeof(seg));124         //memset(pt,0,sizeof(pt));125         memset(c,0,sizeof(c));126         idx = 0;127         for (int i = 0; i < n; i++)128         {129             scanf("%d",a+i);130             vec[idx++] = a[i];131         }132         hash_();133         int LIS = 0;134         for (int i = 0; i < n; i++)135         {136             ans = 0;137             //query(1,n,1,1,a[i]-1);138             query(a[i]-1);139             dp[i] = ans + 1;140             if (ans == 0)141                 pos1[i] = i;142             else143                 pos1[i] = pp;144            // update(1,n,1,a[i],dp[i],pos1[i]);145            add(a[i],dp[i],pos1[i]);146             LIS = max(dp[i],LIS);147         }148         int pre = n;149         for (int i = n -1; i >= 0; i--)150         {151             if (dp[i] != LIS)152                 continue;153             pos2[i] = pre-1;154             pre = i;155         }156         ll cnt = 0;157         for (int i = 0; i < n; i++)158         {159             if (dp[i] != LIS)160                 continue;161             cnt += (ll)(pos1[i] + 1) * (pos2[i]+1-i);162         }163         printf("%I64d\n",cnt);164     }165     return 0;166 }