###### tags: `APCS` `zerojudge` `題解`
# 題解 zerojudge g277:apcs 3. 幸運數字
## set/map/iterator

#include<bits/stdc++.h>
using namespace std;
#define N 300005
long long sum[N]={0};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    set<int>s;
    map<int,int>a;

    int n;cin>>n;
    for(int i=1,k;i<=n;i++){
        cin>>k;
        s.insert(k);
        a[k]=i;
        sum[i]=k+sum[i-1];
    }

    int l=1,r=n;
    auto it=s.begin();
    while(true){
        if(l==r)break;
        int idxm=a[*it];
        while(idxm<l or idxm>r){
            it++;
            idxm=a[*it];
        }
        if(sum[idxm-1]-sum[l-1]>sum[r]-sum[idxm]){
            r=idxm-1;
        }
        else{
            l=idxm+1;
        }
    }
    cout<<sum[l]-sum[l-1];
}