Задача G. Блинчики

Автор:Кривошеева Татьяна   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Мальчик Петя решил приготовить маме подарок на день рождения — праздничный завтрак. Он решил сделать вкусный чай и испечь блинчики. К сожалению, не отличаясь выдающимися кулинарными способностями, Петя не смог уследить за блинчиками. Каждый из них получился подгорелым с одной стороны и недожаренным с другой. В результате у Пети получилось N черно-белых блинчиков. Все блинчики он выложил на большую тарелку друг на друга. Теперь Петя хочет перевернуть их так, чтобы все они лежали светлой стороной вверх — Петя думает, что так они маме понравятся больше. Для переворачивания блинчиков у него есть лопаточка, которой он может взять несколько верхних блинчиков (от одного до всей стопки) и перевернуть их все вместе (таким образом, что верхний блин окажется на месте нижнего из взятых блинов).

За какое минимальное число таких действий Петя может перевернуть все блины светлой стороной вверх?

Формат входного файла

В первой строке входного файла дано число N (1 ≤ N ≤ 100 000) — количество блинчиков. Далее в N строках описываются блинчики, сверху вниз. Если в i-й строке стоит символ W, то i-й блинчик лежит недожаренной стороной вверх, а если B, то подгоревшей стороной вверх.

Формат выходного файла

В выходной файл выведите единственное число — количество переворачиваний, которое должен сделать Петя, чтобы положить все блинчики недожаренной стороной вверх.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
6
W
B
B
B
W
B
4

0.067s 0.009s 13