题目描述

定义"平衡元素"为数组中满足以下条件的元素:

• 若元素是中间元素(位置2到n-1):需左右两个邻居的元素值之和是偶数;
• 若元素是首尾元素(位置1或位置n):仅需唯一邻居的元素值是偶数。

你可以进行若干次操作:选择一个元素，使其数值+1。

给定一个整数数组(长度≥2)，问使所有元素都成为"平衡元素"的最小操作次数。

输入格式

第一行一个正整数n，表示元素个数。 第二行n个正整数ai，分别表示数组中第i个元素值。

输出格式

一行一个整数，表示使所有元素都成为"平衡元素"的最小操作次数。

样例1

4
2 3 5 8

2

样例解释1

使第一位成为平衡元素:给3+1,元素串变为2458; 使第二位成为平衡元素:给5+1，元素串变为2468; 此时第三位(相邻元素分别为4、8)、第四位(相邻元素为6)都是平衡元素。

样例2

5
3 4 5 6 7

0

样例解释2

每个元素都是平衡元素。

数据规模与约定

对于40%的数据，2<=n<=20。

对于100%的数据，2<=n<=100000,1<=ai<=100。