#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#define SIZE 10using namespace std;struct BIGN { int a[SIZE];};inline BIGN operator +(BIGN a,BIGN b){ BIGN c; memset(&c,0,sizeof c); c.a[0]=max(b.a[0],a.a[0]); int jin=0; for(int i=1;i<=c.a[0];i++) { jin+=a.a[i]+b.a[i]; c.a[i]=jin%10000; jin/=10000; } if(jin) c.a[++c.a[0]]=jin; return c;}inline void give(char s[],BIGN &a){ memset(&a,0,sizeof a); int len=strlen(s); int p[4]={1,10,100,1000}; for(int i=len-1,j=0;i>=0;i--,j=(j+1)&3) { if(!j) a.a[0]++; a.a[a.a[0]]=a.a[a.a[0]]+(s[i]-'0')*p[j]; }}inline void prt(BIGN a){ printf("%d",a.a[a.a[0]]); for(int i=a.a[0]-1;i>=1;i--) printf("%04d",a.a[i]); puts("");}BIGN c[6][50010],ans;int n,bh;struct BZ{ int x,h,id;}bz[50010];void read(){ for(int i=1;i<=n;i++) { scanf("%d",&bz[i].x); bz[i].id=i; } }inline bool cmp_x(const BZ &a,const BZ &b){ return a.x<b.x;}inline bool cmp_id(const BZ &a,const BZ &b){ return a.id<b.id;}inline int lowbit(int x){ return x&-x;}void lsh(){ sort(bz+1,bz+1+n,cmp_x); bz[1].h=2; bh=2; for(int i=2;i<=n;i++) { if(bz[i].x!=bz[i-1].x) bz[i].h=++bh; else bz[i].h=bh; } sort(bz+1,bz+1+n,cmp_id);}inline BIGN getsum(int p,int num){ BIGN rt; give("0",rt); while(num) { rt=rt+c[p][num]; num-=lowbit(num); } return rt;} inline void updata(int p,int q,BIGN sy){ while(q<=bh) { c[p][q]=c[p][q]+sy; q+=lowbit(q); }}void go(){ BIGN one,tmp; give("1",one); give("0",ans); for(int i=0;i<=bh;i++) for(int j=1;j<=5;j++) give("0",c[j][i]); for(int i=1;i<=n;i++) { updata(1,bz[i].h,one); for(int j=2;j<=5;j++) { tmp=getsum(j-1,bz[i].h-1); updata(j,bz[i].h,tmp); } } ans=getsum(5,bh); prt(ans);}int main(){ while(scanf("%d",&n)!=EOF) { read(); lsh(); go(); } return 0;}
