ר

11 http:\olimp.bstu.by
17
9:00 12:00

 
HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Unsorted > problem:


Math and Soldiers

Section problems

• Santa Gifts
• Chessboard Pattern
• Galls village
• Sequence
• Bishops
• Polygons
• String manipulations
• Lawyers Council
• Math and Soldiers
• Many-coloured roads
• What about judges?
• Liars and Knights
• Interesting permutations
• Kovrov
• Points
• Roads
• Brackets

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
: , .

The regiment consisting of N mathematicians came to war camp. Commander arranged them in one line and then gave the order "On your left!". Each mathematician knows perfectly, that "left" is a very ambiguous definition, that's why each one turned 90 in arbitrary direction (clockwise or counterclockwise).
As for the punishment, the commander made each soldier to count the number of people this soldier can see and to shout out this number loud.
Soldier A can see soldier B if and only if the following statements are true:

1. A is looking in B direction.
2. There is no one in the line between A and B, or all soldiers between A and B have smaller height than B.

Your task is to write a program that will find out, how many soldiers each soldier does see.

Input
In the first line an integer number N is written - the number of soldiers in a line (1 ≤ N ≤ 105). In the second line the arrangement of soldiers is given, i.e. their directions (angle bracket shows the direction, watch sample for clarification). Angle brackets are separated by spaces. In next N lines numbers Hi are written - the height of i-th soldier (1 ≤ H ≤ 105). People in line are numbered from 1 to N from left to right.
Output
Output file should consist of N lines. In first line should be the number of people that first soldier sees, in second line - the second soldier etc.

Input 1 Output 1 Input 2 Output 2 Input 3 Output 3
2
< >
1
2
0
0
2
> >
1
2
1
0
5
> < < < >
4
2
3
100
1
3
1
2
2
0

.

www.contester.ru