Monk in the Jungle

The Great Monk Maruf is planning to visit the jungle of Amazon. He loves to prepare himself rigorously for his new expeditions. So he has decided to go through everything he has learned in his life so far.

He figured that he learned the following rules about multiplications in his early life:

1. When two negative numbers are multiplied, the result becomes positive.
2. When two positive numbers are multiplied, the result becomes positive.
3. When one positive and one negative number is multiplied, the result becomes negative.
4. When a zero is multiplied with any other number, the result becomes zero.

He wants to make sure he does not forget these important lessons about multiplications when he arrives at Amazon. As a result, he has come up with the following problem:

You will be given an array of integers. Each element of the array will either be negative, or non-negative. You can rearrange the elements of the array by changing the position of the elements. You can only change the order of the elements, but the original elements of the array should remain unchanged. More formally, given an array A, you can take any valid permutation of that array. After the permutation is performed, you need to multiply the elements of the array sequentially from left to right. Let's define partial product Pi, as the multiplication of the first i (1 ≤ i ≤ number_of_elements) values of the permutated array. Two partial products Pi and Pj are adjacent if |i-j| = 1. You have to maximize the number of times the signs of the two adjacent partial products would change. Two signs would be considered the same if they are both positive, both negative or both zero.

Your task is to solve this problem if you want to become a companion of Monk Maruf in the jungle of Amazon.

Input

The first line contains a positive integer T (0 < T ≤ 100000), the size of the array.

In the next T inputs, there will be one number each, the i'th number would indicate the i'th value of the array in initial order. The absolute value of each element of the array will be within 109.

Output

Please print one integer, the maximum number of time the signs of the adjacent partial products of would change.

Samples

Input	Output
3 -1 2 2	1

Input	Output
4 331 234 36777 443	0