Подсчеты в строю
Подсчеты в строю
Весь год Вася не ходил в университет, поэтому не сдал экзамены, и его отчислили. Так он оказался в армии. А одно из самых популярных занятий в армии — стоять в строю.
В Васином взводе n солдат, включая его. Солдаты стоят в одну шеренгу, каждый из них смотрит либо влево, либо вправо, а также имеет свой порядковый номер от 1 до n, равный его месту в шеренге. Рост i-го солдата равен hi
. Вася считает, что солдат с номером i видит солдата с номером j, если выполнены следующие условия:
солдат i смотрит в сторону солдата j;
все солдаты, стоящие между ними, не выше солдата j.
Так, например, если в шеренге стоят 4 солдата ростом h1
= 178, h2
= 180, h3
= 170, h4
= 190, а также все солдаты смотрят влево, то 2-й солдат будет видеть только 1-го, 3-й — только 2-го (так как между ним и первым есть более высокий второй солдат), 4-й будет видеть 2-го и 3-го солдат.
Так как делать в строю все равно больше нечего, Вася хочет посчитать, сколько человек видит каждый из солдат.
Входные данные
Первая строка входных данных содержит число n — количество солдат в шеренге (1 ≤ n ≤ 105)
.
Вторая строка содержит n чисел h1; h2; ... ; hn
— рост солдат в шеренге (1 ≤ hi ≤ 109)
.
Третья строка содержит 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