\(L\) を選ぶ区間，\(A_i\) を選ぶ区間, \(R\) を選ぶ区間に分割する問題とみなしてよいです．

ここで，dp[場所][1つ前の要素をどの区間に分類したか]という状態のdpを考えると，\(\mathrm{O}(N)\) 時間で素直な漸化式で答えが求まります．