В один день BThero решил поиграться с массивами и придумал следующую задачу:
Вам дан массив \(a\), состоящий из \(n\) положительных целых чисел. Массив нумеруется с \(1\) до \(n\). Вы выполняете следующую процедуру ровно один раз:
- Вы создаете новый массив \(b\), состоящий из \(2n\) положительных целых чисел, где для каждого \(1 \le i \le n\) выполнено условие \(b_{2i-1}+b_{2i} = a_i\). Например, для \(a = [6, 8, 2]\) можно создать \(b = [2, 4, 4, 4, 1, 1]\).
- Вы склеиваете подряд идущие одинаковые числа в \(b\). Например, \(b = [2, 4, 4, 4, 1, 1]\) станет \(b = [2, 4, 1]\).
Найдите и выведите минимальное возможное значение \(|b|\) (размер массива \(b\)), которое вы можете получить в конце процедуры. Можно показать, что с заданными ограничениями всегда есть хотя бы один способ построить массив \(b\).
Выходные данные
Для каждого набора входных данных выведите в новой строке одно положительное целое число — минимальное возможное значение \(|b|\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
6 8 2
1
4
3
5 6 6
|
3
1
2
|