Robbery of the array#177

Robbery of the array

1 seconde
256 mégaoctets
Easy

Anton had an array and he loved it very much. He knows some facts about this array:

Once, when returning home, Anton noticed a wicked Grandi next to his array. He could steal one element from the array . You are given an array which is the array that Anton found when he came home. Find the number of ways to add no more than one element to the array to obtain an array that satisfies the conditions above.

Input

The first line contains a single integer (1 \le n \le 10^5) — the number of elements in the array .

The second line contains integers B_i (0 \le B_i \le 1).

Output

Print a single integer — the answer to the problem.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Example 4

Loading
Loading

Example 5

Loading
Loading

Note

Explanation for the first example:

If we add nothing, we get A = [0], which satisfies the conditions.

If we add at the beginning of the array, we get A = [0, , which satisfies the conditions.

If we add at the beginning of the array, we get A = [1, , which does not satisfy the conditions.

If we add at the end of the array, we get A = [0, 0, which satisfies the conditions.

If we add at the end of the array, we get A = [0, 1, which does not satisfy the conditions.

Explanation for the fifth example:

The following arrays satisfy the given conditions: [0,0,0,0, 1,1,1,1], [0,0,0,0,1, 1, [0,0,0,0,1,1, 1, [0,0,0,0,1,1,1,1.