Дзвінок годинникового механізму
Кролики — це маленькі ссавці з родини зайцевих ряду зайцеподібних, як стверджує Вікіпедія. І це правда. Вони не нудні, адже кожен з них унікальний і добре організований. На нашій фермі кролики живуть у захищених загонах, межі яких прикрашені вигадливими квітковими орнаментами. У загонах росте безліч чарівних оранжевих кущиків моркви. Кролики швидко розмножуються (це звичайна справа, щороку народжуються цілі полчища кроликів), і наші наставники прагнуть легко відстежувати їх у загонах.
Загончики організовані впорядковано — вони утворюють один прямий рядок. На початку першого сезону розмноження деякі загончики можуть бути порожніми. Наприкінці кожного сезону розмноження проводиться добре скоординована пересадка кроликів. Пересадка регулюється простою формулою, яка залежить від одного додатного цілого параметра , який можна обрати довільно для кожного сезону. Пересадка здійснюється паралельно для всіх загонів. У кожному загончику приблизно половина кроликів забирається і пересаджується на загонів вниз по рядку. Не має значення, зайнятий цільовий загон чи ні.
Якщо загон знаходиться занадто близько до кінця рядка (менше ніж на загонів вниз по рядку), то всі кролики залишаються в загоні і нікуди не пересаджуються. Будь-який загон може вмістити необмежену кількість кроликів, і в будь-якому непорожньому загоні завжди достатньо кроликів для успішного розмноження.
Дано початкове розташування загонів, яке показує, які з них зайняті кроликами, а які порожні на початку першого сезону розмноження. Визначте мінімальну кількість пересадок, необхідних для того, щоб усі загончики були заселені кроликами.
Вхідні дані
Заданий рядок довжиною символів, де кожен символ представляє один загон і є або (порожній загон), або (зайнятий загон). Перший символ відповідає першому загону в рядку.
Вихідні дані
Виведіть мінімальну кількість пересадок, необхідних для того, щоб усі загончики були заселені кроликами. Якщо заселити всі загончики неможливо при будь-якій кількості пересадок, виведіть .