# CFR 257 D. Sum ( Recursion, Math )

Problem - 257D - Codeforces

The first line contains integer n (1 ≤ n ≤ 1e5) — the size of the array. The second line contains space-separated integers a1, a2, ..., an (0 ≤ ai ≤ 1e9) — the original array. It is guaranteed that the condition ai ≤ ai + 1 ≤ 2·ai fulfills for any positive integer i (i < n).

O( N )

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

void dfs( vector< int > &a, int &neg, int nxt, int x, string &ans ){
if( x < 0 ){ // need positive nxt
neg = 0;
return;
}
if( a[ x ] >= nxt ){ // need positive this, negative nxt, so toggle all signs for nxt
dfs( a, neg, a[ x ] - nxt, x - 1, ans );
ans += "+-"[ neg ];
neg ^= 1;
} else{ // need negative this, positive nxt, so leave nxt as it is
dfs( a, neg, nxt - a[ x ], x - 1, ans );
ans += "+-"[ neg ^ 1 ];
}
}

signed main(){
ios::sync_with_stdio( 0 );
int n; cin >> n;
vector< int > a( n );
for( int i = 0; i < n; ++i ){
cin >> a[ i ];
}
string ans;
{
int neg;
dfs( a, neg, 0, n - 1, ans );
}
cout << ans << endl;
return 0;
}
```