1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5  6 typedef __int64 LL; 7 int n , cnt; 8 const int mod = 1000000007; 9 const int size = 100010;10 LL tree[size];11 int a[size] , b[size];12 13 int lowBit( int x )14 {15     return x & -x;16 }17 18 void update( int x , LL var )19 {20     while( x<=cnt-1 )21     {22         tree[x] += var;23         tree[x] %= mod;24         x += lowBit( x );25     }26 }27 28 LL getSum( int x )29 {30     LL sum = 0;31     while( x )32     {33         sum += tree[x];34         sum %= mod;35         x -= lowBit( x );36     }37     return sum;38 }39 40 LL solve( )41 {42     LL sum = 0;43     int Id;44     LL var;45     for( int i = 1 ; i<=n ; i++ )46     {47         Id = lower_bound( b+1 , b+cnt , a[i] ) - b;48         var = getSum( Id ) + 1;49         sum += var;50         sum %= mod;51         update( Id , var );52     }53     return sum;54 }55 56 int main()57 {58     cin.sync_with_stdio(false);59     int num;60     while( cin >> n )61     {62         memset( tree , 0 , sizeof(tree) );63         for( int i = 1 ; i<=n ; i++ )64         {65             cin >> num;66             a[i] = b[i] = num;67         }68         sort( b+1 , b+n+1 );69         cnt = unique( b+1 , b+n+1 ) - b;70         cout << solve( ) << endl;71     }72     return 0;73 }