На прямой расположено $$$n$$$ фонарей. Фонарь с номером $$$i$$$ находится в позиции $$$i$$$ и имеет мощность $$$p_i$$$.
Каждый фонарь может быть направлен так, чтобы осветить либо несколько фонарей слева, либо несколько фонарей справа. Если $$$i$$$-й фонарь повернут влево, то он освещает все такие фонари $$$j$$$, что $$$j \in [i - p_i, i - 1]$$$. Аналогично, если он повернут вправо, то он освещает все такие фонари $$$j$$$, что $$$j \in [i + 1, i + p_i]$$$.
Вам предстоит выбрать направление для каждого фонаря так, чтобы каждый фонарь освещался хотя бы одним другим фонарем, или сообщить, что это невозможно.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10000$$$) — количество наборов входных данных.
Каждый набор состоит из двух строк. Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — количество фонарей.
Вторая строка содержит $$$n$$$ целых чисел $$$p_1, p_2, \dots, p_n$$$ ($$$0 \le p_i \le n$$$) — мощность $$$i$$$-го фонаря.
Сумма $$$n$$$ по всем наборам входных данных не превышает $$$3 \cdot 10^5$$$.
Для каждого набора входных данных выведите ответ следующим образом:
Если можно направить все фонари так, чтобы каждый фонарь был освещен, выведите YES в первой строке и строку из $$$n$$$ символов L и/или R ($$$i$$$-й символ равен L, если $$$i$$$-й фонарь повернут влево, в противном случае этот символ - R) во второй строке. Если ответов несколько, вы можете вывести любой из них.
Если ответа нет, просто выведите NO для этого набора входных данных.
4 8 0 0 3 1 1 1 1 2 2 1 1 2 2 2 2 0 1
YES RRLLLLRL YES RL YES RL NO
Название |
---|