C. Полей деревья
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В парке находятся $$$n$$$ деревьев, пронумерованных от $$$1$$$ до $$$n$$$. Изначальная высота $$$i$$$-го дерева равна $$$h_i$$$.

Вы хотите полить эти деревья таким образом, чтобы они все выросли до одинаковой высоты.

Процесс полива происходит следующим образом. Вы начинаете поливать деревья в день $$$1$$$. В течение $$$j$$$-го дня вы можете:

  • Выбрать дерево и полить его. Если день нечетный (например, $$$1, 3, 5, 7, \dots$$$), то высота дерева увеличится на $$$1$$$. Если день четный (например, $$$2, 4, 6, 8, \dots$$$), то высота дерева увеличится на $$$2$$$.
  • Или пропустить день без полива какого-либо дерева.

Заметьте, что вы не можете поливать больше одного дерева в день.

Ваша задача — найти минимальное количество дней, необходимое для того, чтобы все деревья выросли до одинаковой высоты.

Вам необходимо ответить на $$$t$$$ независимых наборов тестовых данных.

Входные данные

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — количество наборов тестовых данных.

Первая строка набора тестовых данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — количество деревьев.

Вторая строка набора тестовых данных содержит $$$n$$$ целых чисел $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le 10^9$$$), где $$$h_i$$$ равно высоте $$$i$$$-го дерева.

Гарантируется, что сумма $$$n$$$ по всем наборам тестовых данных не превосходит $$$3 \cdot 10^5$$$ ($$$\sum n \le 3 \cdot 10^5$$$).

Выходные данные

Для каждого набора тестовых данных выведите одно целое число — минимальное количество дней, необходимое для того, чтобы все деревья выросли до одинаковой высоты.

Пример
Входные данные
3
3
1 2 4
5
4 4 3 5 5
7
2 5 4 8 3 7 4
Выходные данные
4
3
16
Примечание

Рассмотрим первый набор тестовых данных примера. Изначальное состояние деревьев выглядит как $$$[1, 2, 4]$$$.

  1. В течение первого дня польем первое дерево, таким образом последовательность высот станет равна $$$[2, 2, 4]$$$;
  2. в течение второго дня польем второе дерево, таким образом последовательность высот станет равна $$$[2, 4, 4]$$$;
  3. пропустим третий день;
  4. в течение четвертого дня давайте польем первое дерево, таким образом последовательность высот станет равна $$$[4, 4, 4]$$$.

Таким образом, ответ равен $$$4$$$.