Untitled

// y.ha
#include <bits/stdc++.h>
#define cook '\n'
#define maxn 100005
#define Task "A"
using namespace std;

int n ;
int a[maxn], SD[maxn], xuoi[maxn], nguoc[maxn], T[maxn] ;
vector<int> v ;

int sumdigit(int x) {
    int s = 0 ;
    while ( x ) {
        s += ( x % 10 ) ;
        x/=10 ;
    }
    return s ;
}

void inp() {
    cin >> n ;
    for ( int i = 1; i <= n; i++ ) {
        cin >> a[i] ;
        SD[i] = sumdigit(a[i]) ;
    }
    v.assign(SD+1, SD+n+1) ;
    sort(v.begin(), v.end()) ;
    v.resize(unique(v.begin(), v.end()) - v.begin()) ;
    for ( int i = 1; i <= n; i++ )
        a[i] = lower_bound(v.begin(), v.end(), SD[i]) - v.begin() + 1 ;
}

int get(int u) {
    int ans = 0 ;
    while ( u ) {
        ans = max(ans, T[u]) ;
        u -= ( u & (-u) ) ;
    }
    return ans ;
}

void add(int u, int val) {
    while ( u <= n ) {
        T[u] = max(T[u], val) ;
        u += ( u & (-u) ) ;
    }
}

void re(int X[maxn]) {
    for ( int i = 1; i <= n/2; i++ ) swap(X[i], X[n-i+1]) ;
}

void reset(int X[maxn]) {
    for ( int i = 1; i <= n; i++ ) X[i] = 0 ;
}

int main()
{
    ios_base::sync_with_stdio(0) ;
    cin.tie(nullptr) ;
    if(fopen(Task".INP","r")) {
        freopen(Task".INP","r",stdin);
        freopen(Task".OUT","w",stdout);
    }
    inp() ;
    for ( int i = 1; i <= n; i++ ) {
        xuoi[i] = get(a[i]-1) + SD[i] ;
        add(a[i], xuoi[i]) ;
    }
    reset(T) ;
    re(a) ;
    re(SD) ;
    for ( int i = 1; i <= n; i++ ) {
        nguoc[i] = get(a[i]-1) + SD[i] ;
        add(a[i], nguoc[i]) ;
    }
    re(SD) ;
    re(nguoc) ;
    int res = -1e9 ;
    for ( int i = 1; i <= n; i++ ) res = max(res, xuoi[i] + nguoc[i] - SD[i] ) ;
    cout << res ;
    return(0) ;
}