19744번 - Counting in the order 다국어

문제

During the whole year Vasya didn't go to the university, therefore he didn't pass his exams and was expelled. That's how he ended up in the army. And the most popular exercise in the army is standing in the order.

There're $n$ soldiers in Vasya's troop including himself. Soldiers are standing in a row, each of them is looking to the left or to the right and have his own serial number from 1ドル$ to $n$ equal to his place in the order. The height of the $i$-th soldier is $h_i$. Vasya thinks that the soldier with number $i$ see the soldier with number $j$ if the following conditions are true:

• soldier $i$ looks toward the soldier $j$;
• all soldiers standing between them are not taller than soldier $j$.

For example, if there're 4ドル$ soldiers in the row with heights $h_1 = 178,ドル $h_2 = 180,ドル $h_3 = 170,ドル $h_4 = 190$ and all soldiers are looking to the left, then 2ドル$-nd soldier will see only the 1ドル$-st one, 3ドル$-rd --- only 2ドル$-nd one (because between him and first soldier there is higher second soldier), 4ドル$-th will see 2ドル$-nd and 3ドル$-rd soldier.

Because there is nothing to do in the order, Vasya wants to calculate how many soldiers see each of the soldiers.

입력

The first line of input contains number $n$ --- the number of soldiers in the row (1ドル \le n \le 10^5$).

The second line contains $n$ numbers $h_1, h_2, \ldots, h_n$ --- heights of soldiers in the row (1ドル \le h_i \le 10^9$).

The third line contains $n$ symbols representing the directions in which the soldiers look: $i$-th symbol is equal <<L>> if $i$-th soldier looks to the left, i.e. potentially can see only the soldiers with serial numbers 1,ドル 2, \ldots, i - 1,ドル or <<R>> if $i$-th soldier looks to the right and potentially can see only the soldier with serial numbers $i + 1, i + 2, \ldots, n$.

출력

Output $n$ integers, where $i$-th integer is equal to the number of soldiers in the row that $i$-th soldier see.

제한

힌트