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