Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Monk in the Jungle

By jackal_1586, TarifEzaz · Limits 1s, 512 MB

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

InputOutput
3
-1 
2
2
1
InputOutput
4
331
234 
36777 
443
0

Discussion

Statistics


62% Solution Ratio

mh755628Earliest, Feb '20

Muhimin_OsimFastest, 0.0s

mh755628Lightest, 131 kB

mdvirusShortest, 186B

Submit

Login to submit

Editorial

Since only the negative numbers have the ability to change signs, you need to count how many negativ...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.