Яхубу стало скучно и он придумал игру, в которую надо играть на бумаге.
Яхуб выписывает n целых чисел a1, a2, ..., an. Каждое из этих целых чисел может быть равно 0 или 1. Ему разрешено выполнить ровно одно действие: выбрать два индекса i и j (1 ≤ i ≤ j ≤ n) и перевернуть все значения ak, позиции которых находятся на отрезке [i, j] (то есть i ≤ k ≤ j). Перевернуть значение x, значит выполнить операцию x = 1 - x.
Цель игры — получить максимальное количество единиц после ровно одного хода. Напишите программу, которая решает маленькую игру Яхуба.
В первой строке содержится целое число n (1 ≤ n ≤ 100). Во второй строке записано n целых чисел: a1, a2, ..., an. Гарантируется, что каждое из этих n чисел равняется либо 0, либо 1.
Выведите целое число — максимальное количество единиц, которое можно получить после ровно одного хода.
В первом случае надо перевернуть отрезок от 2 до 5 (i = 2, j = 5). Такой переворот превращает последовательность в: [1 1 1 0 1]. Итого, в ней теперь четыре единицы. Мы никак не сможем превратить последовательность в [1 1 1 1 1].
Во втором случае, если мы перевернем только второй и третий элементы (i = 2, j = 3), все числа будут равны 1.
9 0 0 1 9 1 0 9 1 1 8 9 9 8 1 9 8 2 2 3 6 3 2 7 3 2 6 7 7 5 3 7 6 3 3 5 6
YES 5 5 6 7 8 9
4 0 0 1 9 1 0 9 1 1 8 9 9 8 1 9 8
NO
3000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач