По итогам учебного года учитель решил поощрить своих учеников — раздать им немного ирисок. Он попросил n учеников встать в ряд. Так как учитель очень пристрастен, то он руководствуется следующим правилом при раздаче ирисок.
Он смотрит на первых двух учеников и даёт больше ирисок тому из них, у которого выше оценки. Если у этих двух учеников одинаковые оценки, то они получают одинаковое количество ирисок. Процесс раздачи проходит аналогичным образом для любой пары рядом стоящих учеников, начиная с первого и заканчивая последним.
Известно, что каждый ученик получит как минимум одну ириску. Вам следует найти, сколько ирисок учитель даёт каждому ученику, таким образом, чтобы общее количество розданных ирисок было наименьшим.
Выходные данные
Содержит n целых чисел, записанных через пробел — сколько ирисок получит каждый ученик в очереди, начиная с первого и заканчивая последним.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
LRLR
|
2 1 2 1 2
|
|
2
|
5
=RRR
|
1 1 2 3 4
|