First, $A_i$ must be even for all $0\leq i \leq N-1$ because after every time we cross $i.5$ moving right we must cross it again in the opposite direction in order to return to 0. We assume $A_i$ is even for the rest of the analysis.
Claim: The optimal number of direction changes is at least $\left(\sum_{i=-1}^{N-1}\frac{|A_i-A_{i+1}|}{2}\right)-1$, where we let $A_{-1}=A_{N}=0$.
Proof: First, consider the case where $A_i<A_{i+1}$. Then Bessie must move right from $i$ to $i+1$ exactly $A_i/2$ times and right from $i+1$ to $i+2$ exactly $A_{i+1}/2$ times. For each R corresponding to moving right from $i+1$ to $i+2$, consider the character preceding it; at most $A_i/2$ of these characters can be Rs. Thus, there must be at least $\frac{A_{i+1}-A_i}{2}$ occurrences of LR in Bessie's route corresponding to changing direction at position $i+1$. We subtract one for $i=-1$, which is a special case because the first character of our route is not preceded by any character.
Similarly, if $A_i>A_{i+1}$, then there must be at least $\frac{A_{i}-A_{i+1}}{2}$ occurrences of RL in Bessie's route corresponding to changing direction at position $i+1$. $\blacksquare$
Next, we show that the optimal number of direction changes is exactly $\left(\sum_{i=-1}^{N-1}\frac{|A_i-A_{i+1}|}{2}\right)-1$ by constructing a route with exactly this number of direction changes. We present two different ways to do this below.
Solution 1:
Greedily move in the current direction (initially right) until we are forced to switch directions. Repeat.
N = int(input()) A = list(map(int, input().split())) + [0] route = [] i = 0 while not (i == 0 and A[i] == 0): while A[i] > 0: # go right as far as possible route.append('R') A[i] -= 1 i += 1 while i > 0 and (A[i-1] > 1 or A[i] == 0): # go left as far as possible route.append('L') i -= 1 A[i] -= 1 print("".join(route))
This solution is correct because it only turns left at positions $i$ where $A_{i-1}>A_{i}$ and only does so $\frac{A_{i-1} - A_{i}}{2}$ times (every time we reach position $i$ after $A_{i}$ becomes $0$), and similarly only turns right at positions where $A_{i-1}<A_{i}$ and only does so $\frac{A_{i} - A_{i-1}}{2}$ times (minus one if $i=0$).
Solution 2:
From $A_{-1},A_0,\dots,A_{N}$ let's construct a sequence of parentheses with length equal to the optimal number of direction changes plus one. Iterate over $i$ from $-1$ to $N-1$. If $A_{i}<A_{i+1}$, then add $\frac{A_{i+1}-A_i}{2}$ left parentheses to our sequence, corresponding to places in the route where we switch directions from L to R. On the other hand, if $A_i>A_{i+1}$, then add $\frac{A_i-A_{i+1}}{2}$ right parentheses to our sequence, corresponding to places in the route where we need to switch directions from R to L. Observe that every proper prefix of our sequence contains more left parentheses than right parentheses (after processing up to $A_i$ the number of left parentheses minus the number of right parentheses is $A_i/2>0$). Also, the total number of left parentheses equals the total number of right parentheses. Thus, given the sequence of parentheses, we can construct a valid route as follows:
The number of direction changes in this route is equal to the length of the sequence minus one, as desired.
N = int(input()) A = list(map(int, input().split())) lparens = [0] * (A[0] // 2) rparens = [] for i in range(N-1): for _ in range((A[i]-A[i+1]) // 2): rparens.append(i+1) for _ in range((A[i+1]-A[i]) // 2): lparens.append(i+1) rparens += [N] * (A[-1] // 2) assert len(lparens) == len(rparens) x = 0 route = [] for l, r in reversed(list(zip(lparens, rparens))): assert x < r while x < r: x += 1 route.append('R') assert x > l while x > l: x -= 1 route.append('L') print("".join(route))