Easy Transform :
Difficulty Level : Easy
Submissions : 31696
Asked In :
Marks :10
: 98 | : 206
You are given $$$N$$$ numbers. You are allowed to perform a "drop" operation where you simply choose any one of the $$$N$$$ given numbers and remove it. After dropping the $$$i$$$-th number: the number to left of it, and the number to right of it become adjacent numbers.
Your task is to minimize the number of drop operations to get a resulting set of numbers where the sum of every two adjacent numbers is even.
Input
First line has a single integer $$$N$$$. Second line has $$$N$$$ space-separated integers.
Constraints
$$$1 \leq N \leq 10^5$$$
$$$-10^4 \leq$$$ each element of the array $$$\leq 10^4$$$
Output
A single integer representing the minimum number of drop operations required.
Example
Input
3 1 2 3
Output
1
