You are given an array of $n$ integers: $a_1, a_2, \ldots, a_n$. Your task is to find some non-zero integer $d$ ($-10^3 \leq d \leq 10^3$) 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 $\lceil\frac{n}{2}\rceil$). 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 $\lceil x \rceil$ 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 \le n \le 100$) — the number of elements in the array.

The second line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$ ($-10^3 \le a_i \le 10^3$).


-----Output-----

Print one integer $d$ ($-10^3 \leq d \leq 10^3$ and $d \neq 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-----
Input
5
10 0 -7 2 6
Output
4
Input
7
0 0 1 -1 0 0 2

Output
0


-----Note-----

In the first sample, $n = 5$, so we need at least $\lceil\frac{5}{2}\rceil = 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.

Difficulty: interview

Starter code:

Solutions:
n=int(input())
ar=list(map(int,input().split()))
pos=0
neg=0
for a in ar:
    if(a>0):pos+=1
    elif a<0:neg+=1
if(pos*2>=n):
    print(1)
elif neg*2>=n:
    print(-1)
else:
    print(0)


n = int(input())
a = list(map(int, input().split()))
p = o = 0
for i in a:
    if i > 0:
        p += 1
    elif i < 0:
        o += 1
if 2 * p >= n:
    print(1)
elif 2 * o >= n:
    print(-1)
else:
    print(0)


n = int(input())
a = [int(i) for i in input().split()]
minus = 0
plus = 0
for el in a:
    if el > 0:
        minus += 1
    elif el < 0:
        plus += 1
if minus >= n // 2 + n % 2:
    print(1)
elif plus >= n // 2 + n % 2:
    print(-1)
else:
    print(0)


import sys
from math import ceil

input = sys.stdin.readline

n = int(input())
a = map(int, input().split())

countPos = 0
countNeg = 0

for i in a:
    if i > 0:
        countPos += 1
    if i < 0:
        countNeg += 1

if countPos >= ceil(n/2):
    print(1)
elif countNeg >= ceil(n/2):
    print(-1)
else:
    print(0)

n = int(input())
a = [int(v) for v in input().split()]

pos, neg, zero = 0, 0, 0
for v in a:
    if v > 0:
        pos += 1
    elif  v <  0:
        neg +=  1
    else:
        zero += 1

if  pos >= n / 2:
    print(1)
elif neg >= n / 2:
    print(-1)
else:
    print(0)


n = int(input())
q = (n + 2 - 1) // 2
s = list(map(int, input().split()))
f = 0
for i in s:
    if(i > 0):
        q -= 1
    elif(i < 0):
        f += 1
if(q <= 0):
    print(1)
elif(f >= (n + 2 - 1) // 2):
    print(-1)
else:
    print(0)

n = int(input())
cl = list(map(int, input().split()))
a = 0
b = 0
for x in cl:
    if x>0:
        a+=1
    if x<0:
        b+=1

if n%2==0:
    k = n//2
else:
    k = n//2+1

if a>=k:
    print(1)
elif b>=k:
    print(-1)
else:
    print(0)


n = int(input())
l = sorted([*list(map(int, input().split()))])

p = sum(1 for e in l if e > 0)
neg = sum(1 for e in l if e < 0)

if p >= (n + 1)//2:
    res = 1
elif neg >= (n + 1) // 2:
    res = -1
else:
    res = 0
print(res)


n = int(input())
a = list(map(int, input().split()))

p = sum([1 for i in a if i > 0])
ng = sum([1 for i in a if i < 0])

if p >= n/2:
    print(1)
elif ng >= n/2:
    print(-1)
else:
    print(0)

n = int(input())
a = list(map(int, input().split()))

pos = sum(x > 0 for x in a)
neg = sum(x < 0 for x in a)

needed = (n + 1) // 2
if pos >= needed:
    print("1")
elif neg >= needed:
    print("-1")
else:
    print(0)

n = int(input())
ai = list(map(int,input().split()))
num = 0
num2 = 0
for i  in range(n):
    if ai[i] > 0:
        num += 1
    elif ai[i] < 0:
        num2 += 1
n2 = n//2 + n % 2
if num >= n2:
    print(1)
elif num2 >= n2:
    print(-1)
else:
    print(0)


n = int(input())
A = list(map(int, input().split()))
cnt1, cnt2 = 0, 0
for i in A:
    if i > 0:
        cnt1 += 1
    elif i < 0:
        cnt2 += 1
if cnt1 >= (n + 1) // 2:
    print(1)
elif cnt2 >= (n + 1) // 2:
    print(-1)
else:print(0)


n = int(input())
li = list(map(int,input().split()))
plus = 0
minus = 0
for i in li:
	if i>0:
		plus += 1
	if i<0:
		minus += 1
if plus >= (n+1)//2:
	print(1)
elif minus >= (n+1)//2:
	print(-1)
else:
	print(0)


N = int(input())
A = [int(a) for a in input().split()]

pos = 0
neg = 0
for a in A:
    if a > 0:
        pos += 1
    elif a < 0:
        neg += 1
        
if pos >= (N+1)//2:
    print(1)
elif neg >= (N+1)//2:
    print(-1)
else:
    print(0)


import math
def A():
    n = int(input())
    a  =  [int(x) for x in input().split()]
    pos , neg = 0 , 0
    for i in a:
        if(i>0): pos+=1
        if(i<0): neg+=1

    if(pos>= math.ceil(n/2)):
        print(1)
        return
    if(neg>= math.ceil(n/2)):
        print(-1)
        return
    print(0)
A()


#!/bin/python3

import math
import os
import random
import re
import sys

n=int(input())
l=list(map(int,input().split()))
a,b=0,0
for i in l:
    if i>0:
        a+=1
    elif i<0:
        b+=1
t=(n+1)//2
if a>=t:
    print(1)
elif b>=t:
    print(-1)
else:
    print(0)

n=int(input())
a=list(map(int,input().split()))
p=0
flag=True
m=0
for i in range(len(a)):
    if a[i]<0:
        m+=1
    if a[i]>0:
        p+=1
if m>p:
    if n//2+n%2<=m:
        print(-1)
        flag=False
else:
    if n//2+n%2<=p:
        print(1)
        flag=False
if flag:
    print(0)


import math
n=int(input())
a=[int(x) for x in input().split()]
co1=co2=co3=0
for item in a:
    if item>0:
        co1+=1
    elif item<0:
        co2+=1
    else:
        co3+=1
if co1>=math.ceil(n/2):
    print(1)
elif co2>=math.ceil(n/2):
    print(-1)
else:
    print(0)
        


n = int(input())
a = [int(s) for s in input().split()]
pol = 0
neg = 0
nul = 0

for el in a:
    if el > 0:
        pol += 1
    elif el < 0:
        neg += 1
    else:
        nul += 1

polov = n//2 + n%2
d = 0
if pol >= polov:
    d = 1
elif neg >= polov:
    d = -1
print(d)

import sys,math,string
input=sys.stdin.readline
from collections import deque
L=lambda : list(map(int,input().split()))
Ls=lambda : list(input().split())
M=lambda : list(map(int,input().split()))
n=int(input())
l=L()
cp=0
cn=0
cz=0
for i in range(n):
    if(l[i]>0):
        cp+=1
    elif(l[i]<0):
        cn+=1
    else:
        cz+=1
if(cp>=(n//2 +(n%2))):
    print(1)
elif(cn>=(n//2 +(n%2))):
    print(-1)
else:
    print(0)


n = int(input())
a = list(map(int, input().split()))
x1, x2 = len([q for q in a if q > 0]), a.count(0)
x3 = n-x1-x2
if x1 >= (n+1)//2:
    print(1)
elif x3 >= (n+1)//2:
    print(-1)
else:
    print(0)


n = int(input())
a = [int(t) for t in input().split(' ')]
plus = len([t for t in a if t > 0])
minus = len([t for t in a if t < 0])

if plus >= n // 2 + n % 2:
    print(1)
elif minus >= n // 2 + n % 2:
    print(-1)
else:
    print(0)


n=int(input())
arr=list(map(int,input().split()))
count1=0
count2=0
count3=0
for i in range(n):
	if(arr[i]==0):
		count1+=1
	elif(arr[i]>0):
		count2+=1
	else:
		count3+=1
if(count2>=count1+count3):
	print(1)
elif(count3>=count1+count2):
	print(-1)
else:
	print(0)