Як увімкнути телевізор?

Обмеження: 2 сек., 256 МіБ

Зима близько. А Зеник та Марічка купили собі будинок та освоюються в ньому.

Виявляється, попередні власники будинку думали, що встановлення великої кількості вимикачів підряд допоможе заощаджувати електроенергію, та це не так. Але Зенику та Марічці тепер приходиться з цим жити.

Щоб увімкнути якийсь прилад потрібно пройти цілий квест. Наприклад, за вимкнення телевізора відповідають \(n\) вимикачів, під’єднаних один за одним.

Кожен із вимикачів має форму квадрата, і може перебувати в одному з двох станів:

• струм може перетікати від верхнього лівого кута до нижнього правого (такий стан позначимо \),

• струм може перетікати від нижнього лівого кута до верхнього правого (такий стан позначимо /).

Усі вимикачі розташовані горизонтально в один ряд. Для кожної пари сусідніх вимикачів верхній правий та нижній правий кут лівого вимикача мають електричні з’єднання з верхнім лівим та нижнім лівим кутами правого вимикача відповідно. Дивіться ілюстрацію до прикладу в розділі Примітки для кращого розуміння.

Також струм підведено до обох входів першого вимикача, а обидва виходи останнього вимикача під’єднані до телевізора.

Зенику відомо у якому стані зараз перебувають усі вимикачі. А яку мінімальну кількість вимикачів потрібно перемкнути, щоб електричний струм потрапив до телевізора і можна було його увімкнути?

Вхідні дані

У першому рядку задано єдине число \(n\) — кількість вимикачів.

У другому рядку задано рядок \(s\) довжини \(n\) який описує стани усіх вимикачів. Якщо \(s_i =\) \, то \(i\)-й вимикач зараз у першому стані, а якщо \(s_i =\) /, то у другому.

Вихідні дані

Виведіть одне число — мінімальну кількість вимикачів, які потрібно перемкнути, щоб увімкнути телевізор.

Обмеження

\(2 \le n \le 10^5\),

\(s\) складається виключно з символів / та \.

Оцінювання задачі складається із наступних блоків:

• 1 бал — перший приклад з умови,

• 1 бал — другий приклад з умови,

• 13 балів — блок тестів у яких \(1 \le n \le 10\),

• 40 балів — блок тестів у яких \(11 \le n \le 1000\),

• 45 балів — блок тестів у яких \(1001 \le n \le 10^5\).

Бали за блок ви отримаєте, лише якщо дасте правильну відповідь на всі тести з блоку.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 /\///	1

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 //\	1

Примітки

Як видно з рисунка — з першого вимикача струм перетікає до другого та з другого до третього. Позиція четвертого вимикача не дозволяє струму перетікати далі.

Але якщо перемкнути лише четвертий вимикач — струм перетече з третього до четвертого, з четвертого до п’ятого, а з п’ятого — до телевізора.