Counting in formation#8262
Vasya skipped university throughout the year, resulting in failed exams and, eventually, expulsion. Consequently, he found himself in the army. One of the most common activities in the army is standing in formation.
In Vasya's platoon, there are soldiers (including Vasya himself). The soldiers stand in a single line, each facing either left or right, and each has a position number from to (corresponding to their place in the line). The height of the -th soldier is h_i. Vasya believes that a soldier with number can see a soldier with number if the following conditions are satisfied:
Soldier is facing towards soldier ;
All soldiers standing between them are not taller than soldier .
For example, suppose there are soldiers in line, with heights h_1 = 178, h_2 = 180, h_3 = 170, h_4 = 190, and all soldiers are facing left. Then, the second soldier can see only the first; the third can see only the second (since between him and the first there is a taller second soldier); and the fourth can see the second and third soldiers.
Since there is little else to do while standing in formation, Vasya wants to determine how many soldiers each person can see.
The first line contains a single integer (1 \le n \le 10^5) — the number of soldiers in the line.
The second line contains integers h_1, h_2, \ldots, h_n (1 \le h_i \le 10^9), the heights of the soldiers in order.
The third line contains characters, each of which is either or , indicating the direction each soldier is facing. The -th character is if the -th soldier is looking to the left (can only potentially see soldiers 1, 2, \ldots, i-1), or if the -th soldier is looking to the right (can only potentially see soldiers i+1, i+2, \ldots, n).
Print integers. The -th number should be equal to the number of soldiers that the -th soldier can see in the line.
Example 1
Example 2
Example 3