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