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≤Ai≤10⁶). Bessie never reaches x>N nor x<0.

Please help Farmer Nhoj count the number of routes Bessie could have taken that are consistent with A and minimize the number of direction changes. It is guaranteed that there is at least one valid route.

#5474 upload 8 done 1 how_to_reg 1

Moo Route timer 1s memory 32MB

#5474

Moo Route 1s 32MB