Вася обожает выставлять сложные фигуры из костяшек домино и, толкнув одну из них, смот- реть, как вся конструкция падает. Однако, он сделал уже так много фигур, что решил придумать что-то новое.
Для своей новой идеи он использует костяшки не только длиной 2, но и более длинные (и более короткие). Все костяшки выстраиваются в одну линию на расстоянии 1, а цель игры опрокинуть все костяшки толкнув наименьшее количество костяшек.
Каждую костяшку можно толкнуть влево или вправо, падая она опрокидывает все костяшки, находящиеся на расстоянии строго меньшем высоты падающей костяшки. При этом те костяшки, которые упали в результате падения на них других костяшек также падают в ту же сторону и, в свою очередь, могут опрокидывать и другие костяшки и так далее.
Формат входных данных
В первой строке записано натуральное число N (0 <= N <= 1 000 000) количество костяшек. Во второй строке записано N натуральных чисел Hi (1 <= Hi <= 1 000 000) высоты костяшек.
Формат выходных данных
Выведите число M наименьшее количество костяшек, которые нужно толкнуть, чтобы вся конструкция упала.
В следующих M строках выведите описание костяшек, которые необходимо толкнуть: номер костяшки (нумерация начинается с единицы и идет слева-направо), а также направление толчка: букву L для толчка влево и R для толчка вправо. Номер костяшки и букву разделяйте пробелом.
Порядок вывода костяшек, которые нужно толкнуть, может быть произвольным. Если решений несколько выведите любое из них
Система оценки
Решения, верно работающие при N <= 1000, будут набирать не менее половины баллов.
| Ввод |
Вывод |
6
1 2 1 4 1 3 |
1
6 L |
7
1 2 4 1 2 3 2 |
2
3 R
2 L |
Замечание
В первом примере последняя костяшка толкается влево, опрокидывая костяшки с номерами 4 и 5 (их высоты 4 и 1 соответственно). Костяшка номер 4 также падает налево и опрокидывает костяшки с номерами 1, 2 и 3.
Во втором примере костяшка номер 3 толкается вправо, опрокидывая костяшки номер 4, 5 и 6.
Костяшка номер 6 также падает вправо и опрокидывает костяшку номер 7. После этого костяшка
номер 2 толкается влево и опрокидывает костяшку номер 1.