Эта задача является усложнённой версией задачи D1, но при этом имеет существенные отличия, поэтому прочитайте условие полностью.
У Поликарпа есть массив из \(n\) (\(n\) — чётное число) целых чисел \(a_1, a_2, \dots, a_n\). Поликарп задумал положительное целое число \(k\). После этого Поликарп стал совершать над массивом операции следующего вида: взять произвольный индекс \(i\) (\(1 \le i \le n\)) и уменьшить число \(a_i\) на \(k\).
После того, как Поликарп совершил некоторое (возможно, нулевое) количество таких операций, оказалось, что не менее половины чисел в массиве стали одинаковыми. Найдите максимальное \(k\), при котором такая ситуация возможна, или выведите \(-1\), если такое число может быть сколь угодно большим.
Выходные данные
Для каждого набора входных данных в отдельной строке выведите одно целое число \(k\) (\(k \ge 1\)) — максимальное возможное число, которое Поликарп использовал в операциях над массивом, или \(-1\), если такое число может быть сколь угодно большим.