Robbery of the array
Anton had an array and he loved it very much. He knows some facts about this array:
The sum of the elements of the array is an even number.
For any (), , where is the size of the array .
.
is an integer.
Once, when returning home, Anton noticed a wicked Grandi next to his array. He could steal one element from the array . You are given an array which is the array that Anton found when he came home. Find the number of ways to add no more than one element to the array to obtain an array that satisfies the conditions above.
Input
The first line contains a single integer () — the number of elements in the array .
The second line contains integers ().
Output
Print a single integer — the answer to the problem.
Examples
Note
Explanation for the first example:
If we add nothing, we get , which satisfies the conditions.
If we add at the beginning of the array, we get 0, , which satisfies the conditions.
If we add at the beginning of the array, we get 1, , which does not satisfy the conditions.
If we add at the end of the array, we get 0, which satisfies the conditions.
If we add at the end of the array, we get 1, which does not satisfy the conditions.
Explanation for the fifth example:
The following arrays satisfy the given conditions: 1, 1, 1, 1.