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
|
|
