Как и многие студенты, Анатолий живёт в общежитии. Как известно, помимо студентов в общежитии также живут тараканы, при этом тараканы бывают двух видов: чёрные и рыжие. У Анатолия в комнате живёт n тараканов.
Однажды Анатолий выстроил всех тараканов в одну шеренгу. Анатолий по своей природе перфекционист, поэтому он хочет, чтобы в шеренге цвета тараканов чередовались. Также у него есть ведро чёрной и ведро рыжей краски. За один ход Анатолий может либо поменять местами любых двух тараканов, либо перекрасить одного из тараканов в другой цвет.
Помогите Анатолию определить, какое минимальное число ходов ему придётся сделать, чтобы цвета всех тараканов в шеренге чередовались?
Выходные данные
Выведите одно число — минимальное количество действий, которые придётся совершить Анатолию, чтобы цвета тараканов в шеренге чередовались.
Примечание
В первом примере Анатолию следует поменять местами третьего и четвертого тараканов. Для этого ему понадобится один ход, поэтому ответ 1.
Во втором примере оптимальным решением будет перекрасить в рыжий цвет второго и четвёртого тараканов. На это потребуется 2 хода.
В третьем примере цвета тараканов в шеренге уже чередуются, поэтому ответ 0.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
rbbrr
|
1
|
|
2
|
5
bbbbb
|
2
|
|
3
|
3
rbr
|
0
|