Вам дан массив из \(n\) целых чисел: \(a_1, a_2, \ldots, a_n\). Ваша задача найти некоторое ненулевое целое число \(d\) (\(-10^3 \leq d \leq 10^3\)) такое, что при делении каждого элемента массива на \(d\) (элементы массива могут перестать быть целыми после этой операции), хотя бы половина чисел в массиве будет положительно (то есть в массиве будет хотя бы \(\lceil\frac{n}{2}\rceil\) положительных чисел). Положительные нецелые числа также считаются положительными, т.е. \(2.5\) будет учтено в подсчете. Если есть несколько подходящих значений \(d\), вы можете вывести любое из них. Если не существует такого \(d\), выведите \(0\).
Напомним, что \(\lceil x \rceil\) обозначает наименьшее целое число, которое больше либо равно \(x\), а \(0\) не является ни положительным, ни отрицательным числом.
Выходные данные
Выведите любое целое число \(d\) (\(-10^3 \leq d \leq 10^3\) и \(d \neq 0\)), подходящее под заданные ограничения. Если есть несколько подходящих значений \(d\), вы можете вывести любое из них. Если не существует такого \(d\), выведите \(0\).
Примечание
В первом примере \(n = 5\), так что нам нужно хотя бы \(\lceil\frac{5}{2}\rceil = 3\) положительных числа после деления. Если \(d = 4\), массив после деления будет \([2.5, 0, -1.75, 0.5, 1.5]\), в котором \(3\) положительных числа (а именно: \(2.5\), \(0.5\), и \(1.5\)).
Во втором примере не существует подходящего \(d\), поэтому должен быть выведен \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
10 0 -7 2 6
|
4
|
|
2
|
7
0 0 1 -1 0 0 2
|
0
|