Дана полоска из \(n\) клеток. В \(i\)-й клетке полоски находится символ \(s_i\), равный '<' или '>'.
Когда шарик помещают в одну из клеток, он начинает движение в соответствии со следующими правилами:
- Если шарик находится в \(i\)-й клетке и \(s_i\) равно '<', то шарик за одну секунду сдвигается на одну клетку влево. Если же \(s_i\) равно '>', то шарик сдвигается на одну клетку вправо.
- После того как шарик сдвинулся, символ \(s_i\) заменяется на противоположный (т. е. если символ \(s_i\) был равен '<', он становится равным '>', и наоборот).
- Шарик прекращает движение, когда покидает полоску: он выходит за границы либо слева, либо справа.
Вам нужно ответить на \(n\) независимых запросов. В \(i\)-м запросе шарик изначально помещается в \(i\)-ю клетку. Обратите внимание, что шарик всегда помещается на одну из клеток изначальной полоски.
Для каждого запроса посчитайте, сколько пройдёт секунд до момента, когда шарик выйдет за пределы полоски. Можно доказать, что шарик всегда покинет полоску за конечное число шагов.
Выходные данные
Для каждого набора входных данных, для каждого \(i\) (\(1 \le i \le n\)) выведите ответ, если шарик изначально помещается в \(i\)-ю клетку.
Примечание
В первом наборе входных данных движение шарика для \(i=1\) показано на картинке ниже. Шарику нужно \(3\) секунды, чтобы покинуть полоску.
Движение шарика для \(i=2\) показано на картинке ниже. Шарику нужно \(6\) секунд, чтобы покинуть полоску.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
><<
4
<<<<
6
<><<<>
|
3 6 5
1 2 3 4
1 4 7 10 8 1
|