ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > Kovrov IT 2008 > задача:


A. Math and Soldiers

Задачи сборника

• A. Math and Soldiers
• B. Roads
• C. Brackets
• D. Bit Decoder
• E. Points
• F. Division
• G. String Multiplication
• H. Lawyers Council

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Павел Кузнецов, ПГУ.

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