Задача CD
На заводі, який виробляє чисті CD-диски, їх
складають в "піраміди" один на одного по N
штук, робочою стороною вниз. Але зрідка трапляється, що диски
складено неправильно, робочою стороною то вниз, то вгору. На заводі є
спеціальний автомат, який може зняти з вершини піраміди будь-яку кількість
дисків і, перевернувши зняту стопку, поставити її на місце так, що нижній знятий
диск опиниться вгорі стопки, не порушуючи порядок розташування дисків, що
перекладаються. За яку мінімальну кількість таких операцій можна всі диски в "піраміді"
розташувати правильно, тобто робочою стороною вниз?
Технічні умови. Програма читає кількість дисків
N (1≤N≤100000), а далі N
чисел (1,
якщо диск лежить робочою стороною вниз і 0,
якщо робочою стороною вгору), починаючи з верхнього диска в "піраміді". Всі числа розділені пропусками. Програма виводить
на екран одне число - мінімальну кількість необхідних операцій. Якщо "піраміду"
"привести в порядок" неможливо, програма виводить -1.
Приклад
Введення
6 1 0 0 0 1 0
Введення
4