Подсчеты в строю
Весь год Вася не ходил в университет, поэтому не сдал экзамены, и его отчислили. Так он оказался в армии. А одно из самых популярных занятий в армии — стоять в строю.
В Васином взводе 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-й солдат в строю.