Алгоритмы — построение последовательности по L/R-операциям

Условие

Дана последовательность A (изначально из одного элемента 0) и строка S длины N из символов <L> и <R>.

Для i = 1, 2, …, N:

• Если S_i = L, вставьте число i слева от числа i − 1 в последовательности A.
• Если S_i = R, вставьте число i справа от числа i − 1 в последовательности A.

Найдите финальную последовательность.

1 ≤ N ≤ 5·10⁵. Лимит памяти: 1024 МБ.

Пример

S = LRRRL → последовательность развивается:

A = (0)
S₁ = L → 1 слева от 0 → (1, 0)
S₂ = R → 2 справа от 1 → (1, 2, 0)
S₃ = R → 3 справа от 2 → (1, 2, 3, 0)
S₄ = R → 4 справа от 3 → (1, 2, 3, 4, 0)
S₅ = L → 5 слева от 4 → (1, 2, 3, 5, 4, 0)

Финал: 1 2 3 5 4 0.