Counting in formation
Throughout the year, Vasya skipped university, resulting in failed exams and eventual 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 n soldiers, including himself. The soldiers stand in a single line, each facing either left or right, and each has a unique position number from 1 to n, corresponding to their place in the line. The height of the i-th soldier is h[i]. Vasya believes that a soldier numbered i can see a soldier numbered j if the following conditions are satisfied:
Soldier i is facing towards soldier j;
All soldiers standing between them are not taller than soldier j.
For instance, if there are 4 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 2-nd soldier will only see the 1-st, the 3-rd will only see the 2-nd (since the second soldier is taller than the first), and the 4-th will see the 2-nd and 3-rd soldiers.
With little else to do in formation, Vasya wants to determine how many soldiers each one can see.
Input
The first line of input contains the number n — the number of soldiers in the line (1 ≤ n ≤ 10^5).
The second line contains n numbers h[1]; h[2]; ... ; h[n] — the heights of the soldiers in the line (1 ≤ h[i] ≤ 10^9).
The third line contains n characters, indicating the direction each soldier is facing:
The i-th character is «L» if the i-th soldier is looking to the left, meaning he can only see soldiers numbered 1; 2; ... ; i - 1, or «R» if the i-th soldier is looking to the right and can only see soldiers numbered i + 1; i + 2; ... ; n.
Output
Print n integers, where the i-th integer represents the number of soldiers that the i-th soldier can see in the line.