201C - Fragile Bridges - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
long long l[maxn],r[maxn],odd[maxn];
int n;
long long a[maxn];
int get(int x)
{
    if(x%2==1)return x-1;
    return x;
}
set<long long>s;
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n-1;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<n-1;i++)
        if(a[i-1]>1)
            l[i]=l[i-1]+get(a[i-1]);
    for(int i=n-2;i>=0;i--)
        if(a[i]>1)
            r[i]=r[i+1]+get(a[i]);
    for(int i=0;i<n-1;i++)
    {
        odd[i]+=get(a[i]-1)+1;
        if(i>0)odd[i]+=odd[i-1];
    }
    long long ans = l[0]+r[0];
    long long tmp = ans;
    s.insert(l[0]);
    for(int i=1;i<n;i++)
    {
        s.insert(l[i]-odd[i-1]);
        long long p=*--s.lower_bound(1LL*1e16);
        ans=max(r[i]+odd[i-1]+p,ans);
    }
    cout<<ans<<endl;
}