N новобранцев стояли перед сержантом, и он приказал им повернуться налево. Некоторые солдаты повернулись налево, остальные повернулись направо. После этого каждый новобранец, увидевший лицо другого новобранца, понял, что совершил ошибку, и повернулся в обратную сторону. Это случилось одновременно для всех пар солдат, стоящих лицом друг к другу. Процесс повторялся до тех пор, пока состояние ряда не стабилизировалось. Напишите программу, которая найдёт, сколько раз развернулись пары солдат, стоящих лицом друг к другу. Если процесс бесконечен, программа должна вывести слово “NO”.
Пример:
Обозначения:
‘<’: новобранец, стоящий лицом влево;
‘>’: новобранец, стоящий лицом вправо.
Строй |
Комментарий |
Количество поворотов |
> > < < > < |
Начальный строй |
2 |
> < > < < > |
Прошла одна секунда |
2 |
< > < > < > |
Прошло две секунды |
2 |
< < > < > > |
Прошло три секунды |
1 |
< < < > > > |
Окончательный строй |
Всего: 7 |
Исходные данные
Первая строка содержит количество новобранцев N. Остаток ввода содержит только символы ‘<’, ‘>’ и переводы строк. Во вводе ровно N символов ‘<’ и ‘>’. В каждой строке может быть до 255 символов.
1 ≤ N ≤ 30 000.
Результат
Выведите количество поворотов.
Пример
исходные данные | результат |
---|
6
>><<>< | 7 |
Источник задачи: Четвертьфинал, центральный регион России, Рыбинск, 17–18 октября 2001