В парке находятся \(n\) деревьев, пронумерованных от \(1\) до \(n\). Изначальная высота \(i\)-го дерева равна \(h_i\).
Вы хотите полить эти деревья таким образом, чтобы они все выросли до одинаковой высоты.
Процесс полива происходит следующим образом. Вы начинаете поливать деревья в день \(1\). В течение \(j\)-го дня вы можете:
- Выбрать дерево и полить его. Если день нечетный (например, \(1, 3, 5, 7, \dots\)), то высота дерева увеличится на \(1\). Если день четный (например, \(2, 4, 6, 8, \dots\)), то высота дерева увеличится на \(2\).
- Или пропустить день без полива какого-либо дерева.
Заметьте, что вы не можете поливать больше одного дерева в день.
Ваша задача — найти минимальное количество дней, необходимое для того, чтобы все деревья выросли до одинаковой высоты.
Вам необходимо ответить на \(t\) независимых наборов тестовых данных.
Выходные данные
Для каждого набора тестовых данных выведите одно целое число — минимальное количество дней, необходимое для того, чтобы все деревья выросли до одинаковой высоты.
Примечание
Рассмотрим первый набор тестовых данных примера. Изначальное состояние деревьев выглядит как \([1, 2, 4]\).
- В течение первого дня польем первое дерево, таким образом последовательность высот станет равна \([2, 2, 4]\);
- в течение второго дня польем второе дерево, таким образом последовательность высот станет равна \([2, 4, 4]\);
- пропустим третий день;
- в течение четвертого дня давайте польем первое дерево, таким образом последовательность высот станет равна \([4, 4, 4]\).
Таким образом, ответ равен \(4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
1 2 4
5
4 4 3 5 5
7
2 5 4 8 3 7 4
|
4
3
16
|