Последовательность \((b_1, b_2, \ldots, b_k)\) называется странной, если модуль разности между любой парой ее элементов больше или равен максимальному элементу этой последовательности. Формально говоря, она странная, если для каждой пары \((i, j)\) с \(1 \le i<j \le k\) выполняется \(|a_i-a_j|\geq MAX\), где \(MAX\) — наибольший элемент последовательности. В частности, любая последовательность длины не более \(1\) является странной.
Например, последовательности \((-2021, -1, -1, -1)\) и \((-1, 0, 1)\) являются странными, а \((3, 0, 1)\) — нет, потому что \(|0 - 1| < 3\).
У Sifid есть массив \(a\) из \(n\) целых чисел. Sifid любит все большое, поэтому среди всех странных подпоследовательностей \(a\) он хочет найти длину самой длинной. Можете ли вы ему помочь?
Последовательность \(c\) является подпоследовательностью массива \(d\), если \(c\) может быть получена из \(d\) путем удаления нескольких (возможно, нуля или всех) элементов.
Выходные данные
Для каждого наборам входных данных выведите одно целое число — длину самой длинной странной подпоследовательности \(a\).
Примечание
В первом наборе входных данных одной из самых длинных странных подпоследовательностей является \((a_1, a_2, a_3, a_4)\).
Во втором наборе входных данных одной из самых длинных странных подпоследовательностей является \((a_1, a_3, a_4, a_5, a_7)\).
В третьем наборе входных данных одной из самых длинных странных подпоследовательностей является \((a_1, a_3, a_4, a_5)\).
В четвертом наборе входных данных одной из самых длинных странных подпоследовательностей является \((a_2)\).
В пятом наборе входных данных одной из самых длинных странных подпоследовательностей является \((a_1, a_2, a_4)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
4
-1 -2 0 0
7
-3 4 -2 0 -4 6 1
5
0 5 -3 2 -5
3
2 3 1
4
-3 0 2 0
6
-3 -2 -1 1 1 1
|
4
5
4
1
3
4
|