#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define rep(i, n) for (int i = 0; i < n; i++) #define rep1(i, n) for (int i = 1; i < n + 1; i++) #define rev(i, n) for (int i = n - 1; i >= 0; i--) #define all(A) A.begin(), A.end() #define itr(A, l, r) A.begin() + l, A.begin() + r #define debug(var) cout << #var << " = " << var << endl; typedef long long ll; template ostream &operator<<(ostream &os, const pair &p) { os << "(" << p.first << "," << p.second << ")"; return os; } template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, const vector &v) { for (int i = 0; i < (int)v.size(); i++) { os << v[i] << (i + 1 != (int)v.size() ? " " : ""); } return os; } template ostream &operator<<(ostream &os, const vector> &v) { for (int i = 0; i < (int)v.size(); i++) { os << v[i] << endl; } return os; } template ostream &operator<<(ostream &os, const vector>> &v) { int n = v.size(); int m = v[0].size(); int p = v[0][0].size(); rep(k, p) { os << "k = " << k << endl; rep(i, n) { rep(j, m) { os << v[i][j][k]; if (j < m - 1) { os << " "; } else { os << endl; } } } } return os; } template istream &operator>>(istream &is, vector &v) { for (T &in : v) is >> in; return is; } template ostream &operator<<(ostream &os, map &mp) { for (auto &[key, val] : mp) { os << key << ":" << val << " "; } cout << endl; return os; } template ostream &operator<<(ostream &os, set st) { auto itr = st.begin(); for (int i = 0; i < (int)st.size(); i++) { os << *itr << (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; } template ostream &operator<<(ostream &os, multiset st) { auto itr = st.begin(); for (int i = 0; i < (int)st.size(); i++) { os << *itr << (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; } template ostream &operator<<(ostream &os, queue q) { while (q.size()) { os << q.front() << " "; q.pop(); } return os; } template ostream &operator<<(ostream &os, deque q) { while (q.size()) { os << q.front() << " "; q.pop_front(); } return os; } template ostream &operator<<(ostream &os, stack st) { while (st.size()) { os << st.top() << " "; st.pop(); } return os; } template ostream &operator<<(ostream &os, priority_queue pq) { while (pq.size()) { os << pq.top() << " "; pq.pop(); } return os; } template ostream &operator<<(ostream &os, priority_queue, greater> mpq) { while (mpq.size()) { os << mpq.top() << " "; mpq.pop(); } return os; } #include using namespace std; using namespace atcoder; using ll = long long; // 単位作用素(区間代入)用の特異値 const ll ID = (ll)8e18; struct S { ll valueSum; // 区間内の値の和 int size; // 区間内の要素数 ll weightSum; // 区間内の重みの和 ll weightedValueSum; // 値×重み の総和 }; using F = ll; // 区間のモノイド結合 S op(S a, S b) { return { a.valueSum + b.valueSum, a.size + b.size, a.weightSum + b.weightSum, a.weightedValueSum + b.weightedValueSum }; } // 単位元 S e() { return {0, 0, 0, 0}; } // 区間への写像(代入演算) S mapping(F f, S x) { if (f != ID) { x.valueSum = f * x.size; x.weightedValueSum = f * x.weightSum; } return x; } // 合成 f 後 g -> g を優先 F composition(F f, F g) { return (f == ID ? g : f); } // 写像の単位元 F id() { return ID; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector h(n); for (int i = 0; i < n; i++) cin >> h[i]; // 値の圧縮&差分による重み作成 vector uq = h; sort(uq.begin(), uq.end()); uq.erase(unique(uq.begin(), uq.end()), uq.end()); vector weight(n); for (int i = 0; i < n; i++) { weight[i] = (i == 0 ? uq[i] : uq[i] - uq[i-1]); } // 初期化 vector init(n); for (int i = 0; i < n; i++) { init[i] = { 0, 1, weight[i], 0 }; } lazy_segtree seg(init); // クエリ処理 for (int i = 0; i < n; i++) { int parity = !(i % 2); int idx = lower_bound(uq.begin(), uq.end(), h[i]) - uq.begin(); // [0, idx+1) 範囲を parity で代入 seg.apply(0, idx+1, (F)parity); // 全区間の重み付き合計を出力 auto all = seg.prod(0, n); cout << all.weightedValueSum << '\n'; } return 0; }