Олимпиадный тренинг

Задача 27042. falling domino


Задача

Темы:
Vasya loves to set up complex pieces of dominoes and, after pushing one of them, watch how the whole structure falls. However, he had already made so many figures that he decided to come up with something new.
For his new idea, he uses dice not only 2 long, but also longer (and shorter). All the tiles line up at a distance of 1, and the goal of the game is to topple all the tiles by pushing the least number of tiles.

Each knuckle can be pushed to the left or right, falling it overturns all the knuckles located at a distance strictly less than the height of the falling knuckle. At the same time, those knuckles that fell as a result of other knuckles falling on them also fall in the same direction and, in turn, can overturn other knuckles, and so on.
 
Input data format
The first line contains the natural number N  (0 <= N <= 1,000,000)      number of bones.  The second line contains N natural numbers Hi (1 <= Hi <= 1 000 000) of the heights of the bones.
Output format
Print the number M, the smallest number of bones that need to be pushed in order for the whole structure to fall.
In the next M lines print a description of the knuckles to be pushed: the number of the knuckle (numbering starts from one and goes from left to right), and the direction of the push: letter L for push to the left and R for push to the right. Separate the number of the bone and the letter with a space.
The order in which the tiles to push can be displayed can be arbitrary. If there are several solutions, print any of them

Rating system
Solutions that work correctly with N <= 1000 will score at least half the points.
 
Input Output
6
1 2 1 4 1 3
1
6 L
7
1 2 4 1 2 3 2
2
3 R
2L
Note
In the first example, the last knuckle is pushed to the left, knocking over knuckles numbered 4 and 5 (their heights are 4 and 1, respectively). The number 4 knuckle also falls to the left and overturns the knuckles numbered 1, 2 and 3.
In the second example, tile number 3 is pushed to the right, knocking over tiles 4, 5, and 6.
The tile number 6 also falls to the right and overturns the tile number 7. After that, the tile
number 2 is pushed to the left and knocks over tile number 1.