Вам даны $$$n$$$ различных целых точек $$$x_1 \lt x_2 \lt \ldots \lt x_n$$$ на оси X на плоскости. Для каждого $$$1 \le i \le n$$$ вам необходимо выбрать действительное значение $$$r_i \gt 0$$$ и нарисовать круг радиусом $$$r_i$$$ и центром в $$$x_i$$$, так чтобы никакие два круга не перекрывались.
Вы хотите выбрать значения $$$r_i$$$ таким образом, чтобы максимизировать количество пар кругов, касающихся друг друга, и вам нужно найти это максимальное значение.
Мы говорим, что два круга перекрываются, если площадь их пересечения положительна. В частности, два круга, касающиеся друг друга, не перекрываются.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2\cdot10^6$$$) — количество точек в этом наборе.
Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$x_1, x_2, \ldots x_n$$$ ($$$0 \le x_1 \lt x_2 \lt \ldots \lt x_n \le 10^9$$$) — координаты точек в этом наборе.
Также гарантируется, что сумма $$$n$$$ по всем наборам не превышает $$$2\cdot10^6$$$.
Для каждого набора входных данных выведите одно целое число, обозначающее максимальное количество пар кругов, касающихся друг друга, в этом наборе.
431 2 341 2 4 561 2 11 12 21 2270 1 2 3 5 8 13
2236
В первом примере вы можете установить $$$r_1 = r_3 = 0.25$$$ и $$$r_2 = 0.75$$$, чтобы 1-й и 2-й круги, а также 2-й и 3-й круги были парно касательными.
Лучшее решение для первого примера. Во втором примере вы можете установить $$$r_1 = 0.4$$$, $$$r_2 = 0.6$$$, $$$r_3 = 0.2$$$ и $$$r_4 = 0.8$$$, чтобы 1-й и 2-й круги, а также 3-й и 4-й круги были парно касательными.
Лучшее решение для второго примера. Лучшее решение в третьем примере — установить $$$r_i = 0.5$$$ для каждого $$$1 \le i \le 6$$$, чтобы 1-й и 2-й круги, 3-й и 4-й круги, а также 5-й и 6-й круги были парно касательными.
