# CFR 314 C. Sereja and Subsequences ( DP, BIT )

Problem - 314C - Codeforces

The first line contains integer n (1 ≤ n ≤ 1e5). The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1e6).

O( N + MAXA lg MAXA )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = ( int ) 1e5;
const int MAXA = ( int ) 1e6;
const int MOD = ( int ) 1e9 + 7;

int N;
int A[ MAXN ];

struct Fenwick_Tree{
int dat[ MAXA + 1 ];
void add( int x, int v ){
for( int i = x; i <= MAXA; i += i & -i ){
( dat[ i ] += v ) %= MOD;
}
}
int sum( int x ){
int res = 0;
for( int i = x; i; i -= i & -i ){
( res += dat[ i ] ) %= MOD;
}
return res;
}
} ftree;

signed main(){
ios::sync_with_stdio( 0 );
cin >> N;
for( int i = 0; i < N; ++i ){
cin >> A[ i ];
}
for( int i = 0; i < N; ++i ){
int v = 1LL * ( ftree.sum( A[ i ] ) + 1 ) * A[ i ] % MOD;
( v -= ( ftree.sum( A[ i ] ) - ftree.sum( A[ i ] - 1 ) ) ) %= MOD;
ftree.add( A[ i ], v );
}
int ans = ftree.sum( MAXA );
if( ans < 0 ) ans += MOD;
cout << ans << endl;
return 0;
}
```