#include using namespace std; using Int = long long; template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a>n; n*=2; vector as(n); for(Int i=0;i>as[i]; vector dp(n+2),pd(n+2); for(Int i=0;i=0;i-=2) pd[i]=pd[i+2]+(as[i+1]-as[i]); Int ans=-1e18; for(Int i=0;i<=n;i+=2) chmax(ans,dp[i]+pd[i]); cout<