/* -*- coding: utf-8 -*- * * 3017.cc: No.3017 莠、莠呈オエ - yukicoder */ #include #include #include #include using namespace std; /* constant */ const int MAX_N = 200000; const int INF = 1 << 30; enum { G, B }; /* typedef */ using pii = pair; using stpii = stack; /* global variables */ int hs[MAX_N]; /* subroutines */ /* main */ int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", hs + i); int sum = 0; stpii q; q.push({INF, G}); for (int i = 0; i < n; i++) { while (q.top().first <= hs[i]) { auto [h, c] = q.top(); q.pop(); if (c == G) sum += h; else sum -= h; } int ci = ((i & 1) == 0) ? B : G; if (q.top().second != ci) { if (ci == G) sum -= hs[i]; else sum += hs[i]; q.push({hs[i], ci}); } printf("%d\n", sum); } return 0; }