Дан массив \(a\) из \(n\) положительных целых чисел.
За одну операцию вы можете выбрать любую пару индексов \((i, j)\) такие, что \(a_i\) и \(a_j\) имеют различную четность, а затем заменить меньший из них на их сумму. Более формально:
- Если \(a_i < a_j\), замените \(a_i\) на \(a_i + a_j\);
- В противном случае замените \(a_j\) на \(a_i + a_j\).
Найдите минимальное количество операций, необходимых для того, чтобы все элементы массива имели одинаковую четность.
Примечание
В первом наборе входных данных все числа уже имеют одинаковую четность, поэтому совершать операции не требуется.
В третьем наборе входных данных мы можем выполнить две операции \((1, 2)\) и \((1, 3)\). Массив \(a\) преобразуется следующим образом: \(a = [\color{red}2, \color{red}3, 4] \longrightarrow [\color{red}5, 3, \color{red}4] \longrightarrow [5, 3, 9]\).
В четвертом наборе входных данных примером оптимальной последовательности операций является \((1, 2)\), \((1, 3)\), \((1, 4)\) и \((1, 4)\). Массив \(a\) преобразуется следующим образом: \(a = [\color{red}3, \color{red}2, 2, 8] \longrightarrow [\color{red}3, 5, \color{red}2, 8] \longrightarrow [\color{red}3, 5, 5, \color{red}8] \longrightarrow [\color{red}{11}, 5, 5, \color{red}8] \longrightarrow [11, 5, 5, 19]\).