#ifndef ONLINE_JUDGE #define _GLIBCXX_DEBUG//[]で配列外参照をするとエラーにしてくれる。上下のやつがないとTLEになるので注意 ABC311Eのサンプル4みたいなデバック中のTLEは防げないので注意 #endif #include #include #include // M_PIを使用するため using namespace std; using ll = long long; using ld = long double; #define rep(i,n) for (ll i = 0; i < (ll)(n); i++) #define rrep(i,n) for (ll i = (ll)n - 1; i >= 0; --i) const ll INF = (1LL << 62); const ll null = -1LL; template using vc = vector;//prioriy_queueに必要なのでここにこれ書いてます template using vv = vc>; template using vvv = vv>; using vl = vc; using vvl = vv; using vvvl = vv; using vvvvl = vv; using vs = vc; using vvs = vv; using vb = vc; using vvb = vc; using P = pair; templateistream& operator>>(istream& i, vc& v) { rep(j, size(v))i >> v[j]; return i; } // それぞれ「下,上,右,左」に対応 int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; #define nall(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define chmax(x,y) x = max(x,y) #define chmin(x,y) x = min(x,y) #define pb push_back #define eb emplace_back #define em emplace #define pob pop_back #define next_p(v) next_permutation(v.begin(),v.end()) void solve() { ll n; cin >> n; vl h(n); cin >> h; ll ans = 0; set> st; st.em(0,INF,1); rep(i,n) { if ((i & 1ll) == 0) { // cyan bool finished = false; auto iter = st.begin(); while (iter != st.end()) { auto [l, r, col] = *iter; if (h[i] < l) break; if (h[i] <= r) { if (col) { ans += h[i] - l; iter = st.erase(iter); st.em(h[i], r, col); } else { st.em(0,r,0); finished = true; } break; } iter = st.erase(iter); if (col) { ans += r - l; } } if (!finished) { st.em(0, h[i], 0); } } else { // green bool finished = false; auto iter = st.begin(); while (iter != st.end()) { auto [l, r, col] = *iter; if (h[i] < l) break; if (h[i] <= r) { if (col == 0) { ans -= h[i] - l; iter = st.erase(iter); st.em(h[i], r, col); } else { st.em(0,r,1); finished = true; } break; } iter = st.erase(iter); if (col == 0) { ans -= r - l; } } if (!finished) { st.em(0, h[i], 1); } } cout << ans << endl; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll testcases = 1ll; // cin >> testcases; rep(_,testcases) solve(); return 0; }