Подотрезок — это непрерывная часть массива.
Ярик недавно нашёл массив \(a\) из \(n\) элементов, и ему стало очень интересно найти сумму непустого подотрезка с максимальной суммой. Но Ярик не любит числа одной чётности, стоящие рядом, так что у подотрезка, который он выберет, чётности соседних элементов должны различаться.
Например, массив \([1, 2, 3]\) подойдёт, но \([1, 2, 4]\) не подойдёт, так как \(2\) и \(4\) — чётные числа и стоят рядом.
Вам нужно помочь Ярику и вывести максимальную сумму такого подотрезка.