Вам дан бинарный массив\(^{\dagger}\) длины \(n\). Вам можете выполнить над ним следующую операцию не более одного раза. Операция заключается в следующем — вы можете выбрать любой элемент и инвертировать его: превратить \(0\) в \(1\) или наоборот.
Какое максимальное количество инверсий \(^{\ddagger}\) может иметь массив после выполнения не более одной операции?
\(^\dagger\) Бинарный массив — это массив, состоящий только из нулей и единиц.
\(^\ddagger\) Количество инверсий в массиве — это количество пар индексов \(i,j\) таких, что \(i<j\) и \(a_i > a_j\).
Примечание
В первом примере инверсии изначально формируются парами индексов (\(1, 2\)), (\(1, 4\)), (\(3, 4\)), что в сумме составляет \(3\), что уже является максимально возможным значением.
Во втором примере инверсии изначально образованы парами индексов (\(2, 3\)), (\(2, 4\)), (\(2, 6\)), (\(5, 6\)), в сумме четыре. Но, применив операцию над первым элементом, массив становится \({1, 1, 0, 0, 1, 0}\), где инверсии уже образованы парами индексов (\(1, 3\)), (\(1, 4\)), (\(1, 6\)), (\(2, 3\)), (\(2, 4\)), (\(2, 6\)), (\(5, 6\)), что в сумме составляет \(7\) инверсий, что является максимально возможным.