Problem G
Bitaflipp

A Turing machine consists of two main parts. Firstly there is a tape divided into small cells, which are numbered in increasing order from $1$. On each cell there is either a $0$ or a $1$. Above this tape here is a head. This head is over one cell at a time, but it can move back and forth between the cells. The head can also read and write on the cell it is over. This machine can then be programmed to solve the same programs as a modern computer.

Figure 1: Image of a Turing machine along with the tape of the first sample.

Gunnar has been practicing programming such Turing machines. The newest program he made starts with the head on cell $i$. The head looks at the number in the current cell. If it is $1$ it writes $0$, but if it is $0$ it writes $1$ over it. Then the head moves to the right. This is repeated until the head is at cell $j$.

As an example, say Gunnar runs the program with $i = 5$ and $j = 7$ on the tape in the image above. The head then starts on cell $5$. The head changes the $0$ to a $1$ and moves to cell $6$. There it changes the $0$ to a $1$ and moves to cell $7$. There it changes the $1$ to a $0$. Then it has arrived at $j = 7$ and stops. Thus the tape will say 1 0 0 1 1 1 0 when the machine is done.

Gunnar quite enjoys this. He has been running his program on different tapes and for different values of $i$ and $j$, which satisfy $1 \leq i \leq j \leq N$ where $N$ is the number of cells on his tape. Now he has a tape he finds very interesting and is wondering what the largest possible number of cells containing a $1$ could be after he runs his program, if he chooses $i$ and $j$ optimally.

Input

On the first line there is an integer $N$ denoting the number of cells in the tape. Then there is a line with $N$ numbers, each either $0$ or $1$, which denote the initial contesnts of the cells, ordered from $1$ to $N$.

Output

The output should contain a single line with an integer denoting the highest possible number of cells containing a $1$ after the program is run, if $i$ and $j$ are chosen in the best way possible.

Explanation of Sample Inputs

The tape in the first sample is shown in the image above. It contains $7$ cells. In this sample the highest number of cells that contain a $1$ after the program is run is $6$, when $i = 2$ and $j = 6$ are chosen.

In the second sample all cells already contain the number $1$. But Gunnar must run the program exactly once. If he runs the program with $i = 1$ and $j = 1$ then there are $2$ cells left with the value $1$, and this is the best result possible.

Scoring

The solution will be tested on differently hard input data and the data is divided into groups as shown in the table below. The solution will then be scored according to how many groups are solved.

7
1 0 0 1 0 0 1

6

3
1 1 1

2