Лимак — маленький мишка, который любит играть. Он строит башенки из кубиков, а потом рушит их.
Он возвёл n башен, расположенных в ряд, i-я башня сделана из hi одинаковых кубиков. (смотрите иллюстрацию к первому примеру).
Лимак повторит следующую операцию, пока конструкция не разрушится целиком.
Кубик называется внутренним, если у него есть все четыре соседа, то есть если каждая его сторона (левая, правая, верхняя или нижняя) примыкает к другому кубику или к полу. В противном случае, кубик считается граничным. За одну операцию Лимак одновременно разрушает все граничные кубики.
Лимак готов начинать. Ваша задача — посчитать, сколько операций ему будет нужно, чтобы уничтожить все кубики.
Примечание
Приведенная ниже иллюстрация показывает все три операции для первого теста. Каждый раз граничные кубики окрашены красным.
После первой операции остается четыре кубика, а после второй операции остается только один. Этот последний кубик уничтожается в третьей операции.