You are given an array of n integers: a1,a2,…,an. Your task is to find some non-zero integer d (−103≤d≤103) such that, after each number in the array is divided by d, the number of positive numbers that are presented in the array is greater than or equal to half of the array size (i.e., at least ⌈n2⌉). Note that those positive numbers do not need to be an integer (e.g., a 2.5 counts as a positive number). If there are multiple values of d that satisfy the condition, you may print any of them. In case that there is no such d, print a single integer 0.
Recall that ⌈x⌉ represents the smallest integer that is not less than x and that zero (0) is neither positive nor negative.

Input
The first line contains one integer n (1≤n≤100) — the number of elements in the array.
The second line contains n space-separated integers a1,a2,…,an (−103≤ai≤103).

Output
Print one integer d (−103≤d≤103 and d≠0) that satisfies the given condition. If there are multiple values of d that satisfy the condition, you may print any of them. In case that there is no such d, print a single integer 0.

Examples
inputCopy
5
10 0 -7 2 6
outputCopy
4

inputCopy
7
0 0 1 -1 0 0 2
outputCopy
0

Note
In the first sample, n=5, so we need at least ⌈52⌉=3 positive numbers after division. If d=4, the array after division is [2.5,0,−1.75,0.5,1.5], in which there are 3 positive numbers (namely: 2.5, 0.5, and 1.5).
In the second sample, there is no valid d, so 0 should be printed.

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n; scanf("%d",&n);
	int num1=0,num2=0;
	for(int i=1;i<=n;i++){
		int a; scanf("%d",&a);
		if(a>0) num1++;
		else if(a<0) num2++;
	} 
	int num=(n/2)+(n%2==1);
	if(num1>=num) puts("1");
	else if(num2>=num) puts("-1");
	else puts("0");
	return 0;
}