Решение задачи Домино с Codeforces

У Валеры имеется n костей домино, выложенных в ряд. Каждая кость состоит из двух половинок — верхней и нижней. На каждой из половинок записано число от 1 до 6. Валера очень любит четные числа, поэтому он хочет, чтобы сумма чисел, записанных на верхних половинках, и сумма чисел, записанных на нижних половинках, были четными.

Для того, чтобы это произошло, Валера может поворачивать кости на 180 градусов. После поворота верхняя и нижняя половинки кости меняются местами. Данное действие занимает у Валеры одну секунду. Помогите Валере узнать, какое минимальное количество времени он должен потратить на повороты домино, чтобы его желание исполнилось.