1 #include
     
       2 #include
      
        3 #define MOD 1000000007 4 __int64 ans[100005],c[100005]; 5 int a[100005],wei[100005],n; 6 void sort(int l,int r) 7 { 8     int i,j,x,y,x1; 9     x=a[(l+r)/2]; x1=wei[(l+r)/2];10     i=l; j=r;11     while (i<=j)12     {13         while (a[i]
       
        
         x1)) j--;15         if (i<=j)16         {17             y=a[i]; a[i]=a[j]; a[j]=y;18             y=wei[i]; wei[i]=wei[j]; wei[j]=y;19             i++; j--;20         }21     }22     if (i
         
          0){33         ret=(ret+c[x])%MOD;34         x-=lowbit(x);35     }36     return ret;37 }38 void add(int x,__int64 d)39 {40     while (x<=n){41         c[x]=(c[x]+d)%MOD;42         x+=lowbit(x);43     }44 }45 int main()46 {47     int i;48     __int64 aa;49     while (~scanf("%d",&n))50     {51         for (i=1;i<=n;i++) 52         {53             scanf("%d",&a[i]);54             ans[i]=1; wei[i]=i;55         }56         sort(1,n);57         memset(c,0,sizeof(c));58         for (i=1;i<=n;i++)59         {60             ans[wei[i]]=(1+sum(wei[i]-1))%MOD;61             add(wei[i],ans[wei[i]]);62             63         }64         printf("%I64d\n",sum(n));65     }66 }