#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair P; typedef pair Pid; typedef pair Pdi; typedef pair Pl; typedef pair> PP; const double PI = 3.1415926535897932; // acos(-1) const double EPS = 1e-15; const int INF = 1001001001; const int mod = 1e+9 + 7; #define chmax(x, y) x = max(x, y) #define chmin(x, y) x = min(x, y) #define chadd(x, y) x = (x + y) % mod template struct SegmentTree{ using F = function; int sz; vector seg; const F f; // モノイドに対して二項演算を行う関数オブジェクト const Monoid M1; SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1){ sz = 1; while(sz < n) sz <<= 1; seg.assign(2 * sz, M1); } void set(int k, const Monoid &x){ seg[k + sz] = x; } void build(){ for(int k = sz - 1; k > 0; --k){ seg[k] = f(seg[k << 1], seg[k << 1 | 1]); } } void update(int k, const Monoid &x){ k += sz; seg[k] = x; while(k >>= 1){ seg[k] = f(seg[k << 1], seg[k << 1 | 1]); } } Monoid query(int a, int b){ Monoid L = M1, R = M1; for(a += sz, b += sz; a < b; a >>= 1, b >>= 1){ if(a & 1) L = f(L, seg[a++]); if(b & 1) R = f(seg[--b], R); } return f(L, R); } Monoid operator[](const int &k) const{ return seg[k + sz]; } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; int sz = n * 2; SegmentTree evenseg(sz, [](ll a, ll b){return a + b;}, 0); SegmentTree oddseg(sz, [](ll a, ll b){return a + b;}, 0); for(int i = 0; i < sz; ++i){ ll input; if(i % 2 == 0){ cin >> input; evenseg.update(i, input); } else{ cin >> input; oddseg.update(i, input); } } ll res = -1e+16; for(int i = 0; i < sz; i += 2){ ll foo = evenseg.query(0, i) + oddseg.query(i, sz); ll bar = evenseg.query(i, sz) + oddseg.query(0, i); chmax(res, foo - bar); } cout << res << endl; }