eolymp
bolt
Try our new interface for solving problems
Məsələlər

Подсчеты в строю

Подсчеты в строю

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Весь год Вася не ходил в университет, поэтому не сдал экзамены, и его отчислили. Так он оказался в армии. А одно из самых популярных занятий в армии — стоять в строю.

В Васином взводе 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-го солдат.

Так как делать в строю все равно больше нечего, Вася хочет посчитать, сколько человек видит каждый из солдат.

Giriş verilənləri

Первая строка входных данных содержит число 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.

Çıxış verilənləri

Выведите n целых чисел, i-е из выведенных чисел должно быть равно числу солдат, которых видит i-й солдат в строю.

Nümunə

Giriş verilənləri #1
4
178 180 170 190
LLLL
Çıxış verilənləri #1
0 1 1 2
Giriş verilənləri #2
5
178 180 175 170 190
LLRLL
Çıxış verilənləri #2
0 1 2 2 3
Giriş verilənləri #3
5
178 180 170 170 160
LLRLL
Çıxış verilənləri #3
0 1 1 2 3
Mənbə Джерело XXV Командный чемпионат школьников Санкт-Петербурга по программированию Санкт-Петербург, Университет ИТМО, 5 ноября 2017 года