Підрахунок у шерензі#8262
Весь рік Вася не ходив до університету, тому не склав іспити, і його відрахували. Так він потрапив до армії. Одне з найпопулярніших занять в армії — стояти у шерензі.
У взводі Васі військових, разом з ним. Військові стоять в одну шеренгу, кожен із них дивиться або вліво, або вправо, а також має свій порядковий номер від до , що дорівнює його місцю в шерензі. Зріст -го військового дорівнює h_i. Вася вважає, що військовий з номером бачить військового з номером , якщо виконуються наступні умови:
військовий дивиться у бік військового ;
усі військові, що стоять між ними, не вище військового .
Наприклад, якщо в шерензі стоять військових зі зростом h_1 = 178, h_2 = 180, h_3 = 170, h_4 = 190, і всі дивляться вліво, то другий військовий бачить лише першого; третій — лише другого (оскільки між ним і першим є вищий другий військовий), а четвертий бачить другого і третього військового.
Оскільки займатися у шерензі все одно немає чим, Вася хоче підрахувати, скільки людей бачить кожен із військових.
Перший рядок вхідних даних містить число (1 \le n \le 10^5) — кількість військових у шерензі.
Другий рядок містить чисел h_1, h_2, \ldots, h_n (1 \le h_i \le 10^9) — зріст військових у шерензі.
Третій рядок містить символів, що описують напрямки погляду: -й символ дорівнює , якщо -й військовий дивиться вліво, тобто може побачити лише військових з номерами 1, 2, \ldots, i - 1, або , якщо -й військовий дивиться вправо, тобто може побачити лише військових з номерами i + 1, i + 2, \ldots, n.
Виведіть цілих чисел, -те з виведених чисел повинне дорівнювати кількості військових, яких бачить -й військовий у шерензі.
Приклад 1
Приклад 2
Приклад 3