Maximize Social Distancing

You are given a list of integers seats containing 1s and 0s. Each element seats[i] represents a seat and is either occupied if seats[i] = 1 or empty if seats[i] = 0.

Given that there’s at least one empty seat and at least one occupied seat, return the maximum distance from an empty seat to the closest occupied seat.

Constraints

• n ≤ 100,000 where n is the length of seats

https://binarysearch.com/problems/Maximize-Social-Distancing

Examples

Example 1

Input

• seats = [1, 0, 1, 0, 0, 0, 1]

Output

• answer = 2

Explanation

We can sit at seats[4].

Example 2

Input

• seats = [1, 0, 0, 0]

Output

• answer = 3

Explanation

We can sit at seats[3].

Solution