1986: [USACO 2023 January Contest Gold] Problem 3. Moo Route

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,\dots ,(N-1).5$, given by an array $A_0,A_1,\dots ,A_{N-1}$ ($1\le N\le {10}^5$, $1\le A_i\le {10}^6$). Bessie never reaches $x>N$ nor $x<0$.

In particular, Bessie's route can be represented by a string of $T=\sum _{i=0}^{N-1}{A}_i$ $L$s and $R$s where the $i$th character represents the direction Bessie moves in during the $i$th second. The number of direction changes is defined as the number of occurrences of $LR$s plus the number of occurrences of $RL$s.

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.

2
4 6

2