from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations
from heapq import heappop, heappush
import math
_int = lambda x: int(x)-1
MOD = 998244353
INF = 1<<60
Yes, No = "Yes", "No"

N = int(input())
H = list(map(int, input().split()))

q = []
ans = 0
for i in range(N):
    h = H[i]
    if i%2 == 0:
        while q:
            l, r = q.pop()
            if r <= h:
                ans -= r-l
            elif l > h:
                q.append((l, r))
                break
            else:
                h = r
                ans -= r-l
                break
        q.append((0, h))
        ans += h
    else:
        while q:
            l, r = q.pop()
            if l > h:
                q.append((l, r))
                break
            elif r <= h:
                ans -= r-l
            else:
                q.append((h, r))
                ans -= h-l
                break
    print(ans)