Задача №114835. Подсчеты в строю
Весь год Вася не ходил в университет, поэтому не сдал экзамены, и его отчислили. Так он оказался в армии. А одно из самых популярных занятий в армии — стоять в строю.
В Васином взводе n солдат, включая его. Солдаты стоят в одну шеренгу, каждый из них смотрит либо влево, либо вправо, а также имеет свой порядковый номер от 1 до n , равный его месту в шеренге. Рост i -го солдата равен h i . Вася считает, что солдат с номером i видит солдата с номером j , если выполнены следующие условия:
- солдат i смотрит в сторону солдата j ;
- все солдаты, стоящие между ними, не выше солдата j .
Так, например, если в шеренге стоят 4 солдата ростом h 1 = 178 , h 2 = 180 , h 3 = 170 , h 4 = 190 , а также все солдаты смотрят влево, то 2 -й солдат будет видеть только 1 -го, 3 -й — только 2 -го (так как между ним и первым есть более высокий второй солдат), 4 -й будет видеть 2 -го и 3 -го солдат.
Так как делать в строю все равно больше нечего, Вася хочет посчитать, сколько человек видит каждый из солдат.
Первая строка входных данных содержит число n — количество солдат в шеренге ( 1 ≤ n ≤ 10 5 ).
Вторая строка содержит n чисел h 1 , h 2 , ..., h n — рост солдат в шеренге ( 1 ≤ h i ≤ 10 9 ).
Третья строка содержит n символов, описывающих направление, в которые смотрят солдаты: i -й символ равен « L », если i -й солдат смотрит влево, то есть потенциально может увидеть только солдат с номерами 1, 2, ..., i - 1 , либо « R », если i -й солдат смотрит вправо и потенциально может увидеть только солдат с номерами i + 1, i + 2, ..., n .
Выведите n целых чисел, i -е из выведенных чисел должно быть равно числу солдат, которых видит i -й солдат в строю.
4 178 180 170 190 LLLL
0 1 1 2
5 178 180 175 170 190 LLRLL
0 1 2 2 3
5 178 180 170 170 160 LLRLL
0 1 1 2 3