Вам задан массив \(a\), состоящий из \(n\) целых чисел. Индексы элементов массива начинаются с нуля (то есть первый элемент — это \(a_0\), второй — \(a_1\), и так далее).
Вы можете развернуть не более одного подмассива (последовательного отрезка) этого массива. Напомним, что подмассив \(a\) с границами \(l\) и \(r\) равен \(a[l; r] = a_l, a_{l + 1}, \dots, a_{r}\).
Ваша задача — развернуть такой подмассив, чтобы сумма элементов на четных позицияx получившегося массива была максимально возможной (то есть сумма элементов \(a_0, a_2, \dots, a_{2k}\) для целого числа \(k = \lfloor\frac{n-1}{2}\rfloor\) должна быть максимально возможной).
Вам необходимо ответить на \(t\) независимых наборов тестовых данных.