Moo Route timer 1s memory 32MB

Farmer Nhoj dropped Bessie in the middle of nowhere! At time t=0, Bessie is located at x=0 on an infinite number line. She frantically searches for an exit by moving left or right by 1 unit each second. However, there actually is no exit and after T seconds, Bessie is back at x=0, tired and resigned.

Farmer Nhoj tries to track Bessie but only knows how many times Bessie crosses x=.5, 1.5, 2.5, …,(N−1).5

, given by an array A₀,A₁,…,A_N−1 (1≤N≤10⁵, 1≤A_i≤10⁶, ∑A_i≤10⁶). Bessie never reaches x>N nor x<0.

Please help Farmer Nhoj find any route Bessie could have taken that is consistent with A and minimizes the number of direction changes. It is guaranteed that there is at least one valid route.​