P15594 [ICPC 2020 Jakarta R] Exchange Bottleneck

The country of Bazbesonin currently has $N$ cities (numbered from $1$ to $N$) connected by bidirectional roads. When a pair of cities, $u$ and $v$, would like to exchange a message, the **latency** is defined as the minimum number of roads required to go from $u$ to $v$. These cities have a long history in the past. Initially, city $1$ is constructed in the middle of Bazbesonin. Thereafter, the rest of the cities are constructed one after another from city $2$ to city $N$. When constructing city $x$, one or more bidirectional roads were also constructed depending on the economic condition of Bazbesonin at that time. - If city $x$ was constructed when the economy was good, the roads connecting city $x$ and all cities constructed previously were constructed. In other words, the roads connecting city $x$ and city $y$ were constructed, for all $1 \leq y < x$. - If city $x$ was constructed when the economy was bad, only the road connecting city $x$ and city $x-1$ was constructed. The economic condition of Bazbesonin is represented by the binary array $E_{1...N-1}$. If the economy was good when city $x$ was constructed, then the value of $E_{x-1}$ is $1$. Otherwise, the value of $E_{x-1}$ is $0$. Back to the present day, each of the $N$ cities would like to exchange a message with every other city. The bottleneck of the exchange is the maximum latency among all pairs of cities. We would like to compute the bottleneck of the message exchange. For example, let $N = 5$ and $B_{1...4} = [1, 0, 1, 0]$. The cities and roads in Bazbesonin can be illustrated by the following figure: :::align{center}  ::: - The latency of city $1$ and city $2$ is $1$. - The latency of city $1$ and city $3$ is $2$. - The latency of city $1$ and city $4$ is $1$. - The latency of city $1$ and city $5$ is $2$. - The latency of city $2$ and city $3$ is $1$. - The latency of city $2$ and city $4$ is $1$. - The latency of city $2$ and city $5$ is $2$. - The latency of city $3$ and city $4$ is $1$. - The latency of city $3$ and city $5$ is $2$. - The latency of city $4$ and city $5$ is $1$. Therefore, the bottleneck in this example is $2$.

Input begins with a line containing an integer: $N$ ($2 \leq N \leq 100\,000$) representing the number of cities in Bazbesonin. The next line contains $N-1$ integers: $E_i$ ($E_i \in \{0,1\}$) representing the economic condition of Bazbesonin.

Output in a line an integer representing the bottleneck of the message exchange.

#### Explanation for the sample input/output #1 This is the example from the problem description. #### Explanation for the sample input/output #2 Each pair of cities is connected by a road, and thus their latencies are $1$.