Pear Trees and Apple Trees

Interview

Time limit1sMemory limit128 MB

Summary

Find the largest distance between any pear tree and any apple tree in a row of n trees.

Level: Easy2 of 10
Topics: Array
Solved: No attempts yet

Problem

In an orchard, pear trees and apple trees are all planted along a straight line, each spaced $1$ meter apart from the next. The orchard's owner, Mr. Wiktor, wants to find the pear tree that is farthest from any apple tree. Help him by computing the maximum distance between a pear tree and an apple tree.

Input

The first line contains an integer $n$ ( $2 \le n \le 10^6$ ), the number of trees in the orchard. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ separated by spaces. Each $a_i$ gives the type of the $i$ -th tree: $0$ means a pear tree and $1$ means an apple tree. You may assume the orchard contains at least one pear tree and at least one apple tree.

Output

Print a single integer: the maximum distance between a pear tree and an apple tree. Because adjacent trees are $1$ meter apart, the distance between the $i$ -th and $j$ -th trees is $|i - j|$ meters.

Examples5

Example 1
Input
```
5
0 1 1 0 0
```
Expected output
```
3
```
Example 2
Input
```
2
0 1
```
Expected output
```
1
```
Example 3
Input
```
2
1 0
```
Expected output
```
1
```
Example 4
Input
```
6
0 0 0 1 1 1
```
Expected output
```
5
```
Example 5
Input
```
8
0 1 0 1 0 1 0 1
```
Expected output
```
7
```