В ряд вдоль одной линии стоят \(n\) человек, каждый смотрит либо влево, либо вправо.
Каждый человек посчитал количество людей, которое он видит (то есть количество человек в направлении его взгляда). Назовём величиной ряда сумму посчитанных значений.
Например, если люди стоят следующим образом: LRRLL, где L обозначает человека в направлении «влево», а R обозначает человека в направлении «вправо», то посчитанные значения равны \([0, 3, 2, 3, 4]\), а величина ряда равна \(0+3+2+3+4=12\).
Вам задано начальное расположение людей вдоль линии. Для каждого \(k\) от \(1\) до \(n\), определите максимальную возможную величину ряда, если вы можете изменить направление не более чем у \(k\) человек.
Выходные данные
Для каждого набора входных данных выведите \(n\) целых чисел — для всех \(k\) от \(1\) до \(n\) выведите максимальное значение ряда, если можно изменить направление не более чем \(k\) человек в ряду.
Примечание
В первом наборе входных данных примера:
- \(k=1\): изменим направление \(1\)-го человека, чтобы достичь состояния RLR. В этом случае величина ряда равна \(2+1+0=3\).
- \(k=2\): изменим направление \(2\)-х человек, чтобы ряд принял вид RLL. В этом случае величина ряда будет равна \(2+1+2=5\).
- \(k=3\): изменим направление \(2\)-х человек, чтобы ряд принял вид RLL. В этом случае величина ряда будет равна \(2+1+2=5\) (обратите внимание, что можно менять направление \(k\) или меньше людей).
Во втором наборе входных данных примера для каждого \(k\) от \(1\) до \(5\) достаточно только лишь менять направление одного первого человека (чтобы ряд принял вид RRRLL).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3
LLR
5
LRRLL
1
L
12
LRRRLLLRLLRL
10
LLLLLRRRRR
9
LRLRLRLRL
|
3 5 5
16 16 16 16 16
0
86 95 98 101 102 102 102 102 102 102 102 102
29 38 45 52 57 62 65 68 69 70
44 50 54 56 56 56 56 56 56
|