Jogo da Maior Soma

O Jogo da Maior Soma é uma atração de um programa televisivo onde a pontuação do participante é determinada da seguinte maneira. São disposto $N$ números inteiros em um painel digital, numa sequência ordenada de quadrados que forma um retângulo de dimensões $1\times N$, onde $N$ é um número par. Em cada uma das $N/2$ rodadas o participante deve escolher ou o número que está mais à esquerda ou o número que está mais à direita do retângulo, e o valor escolhido será adicionado a sua pontuação. O número escolhido é removido do retângulo e então inicia-se a próxima rodada.

Dados os valores de $N$ e os números na ordem apresentada no painel, determine qual é a pontuação máxima que pode ser obtida pelo jogador e uma sequência de escolhas que leve a esta pontuação máxima.

Entrada

A primeira linha da entrada contém o valor de $N$ $(2\leq N\leq 10^5)$, onde $N$ é um número par. Na linha seguinte estão os $N$ inteiros $n_i$ $(-100\leq n_i\leq 100, 1\leq i\leq N)$, separados por um espaço em branco, na ordem apresentada no painel, da esquerda para a direita.

Saída

Imprima, em uma linha, a pontuação máxima que pode ser obtida pelo jogador. Na linha seguinte imprima uma sequência de escolhas que leve à pontuação máxima, usando o caractere L para indicar a escolha do elemento da esquerda e R para o elemento da direita. Caso exista mais de uma sequência que leve à pontuação máxima, imprima qualquer uma delas.

Exemplo de entrada 1

6
-3 8 0 3 -5 1

Exemplo de saída 1

6
LLR

Exemplo de entrada 1: No primeiro caso, ao pegar os dois elementos à esquerda e o elemento da direita, obtem-se $-3 + 8 + 1 = 6$, que é a maior pontuação possível dadas as regras do jogo.

Exemplo de entrada 2

4
10 -11 9 -8

Exemplo de saída 2

2
RL

Exemplo de entrada 2: No segundo caso, há apenas 3 escolhas possíveis para os elementos: LL, LR e RR. Dentre as três, a escolha RL (que equivale a sequência LR) gera a maior pontuação possível.

Exemplo de entrada 3

10
-1 -3 -2 -4 2 1 -8 -3 0 -1

Exemplo de saída 3

-7
LRLLR

Exemplo de entrada 3: No terceiro caso, observe que a pontuação máxima pode ser negativa, pois não há a opção de não se escolher um dos dois números disponíveis.