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, 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. Initially, city 1 was built in the middle of Bazbesonin. After that, the remaining cities were built one after another, from city 2 to city N. When city x was built, one or more bidirectional roads were also built depending on the economic condition of Bazbesonin at that time.

• If city x was built when the economy was good, roads connecting city x to all previously built cities were built. In other words, for every 1 ≤ y < x, a road connecting city x and city y was built.
• If city x was built when the economy was bad, only the road connecting city x and city x − 1 was built.

The economic condition of Bazbesonin is represented by the binary array E1...N−1. If the economy was good when city x was built, the value of Ex−1 is 1. Otherwise, the value of Ex−1 is 0.

In the present day, each of the N cities wants to exchange a message with every other city. The bottleneck of the exchange is the maximum latency over all pairs of cities. We want to compute the bottleneck of the message exchange.

For example, let N = 5 and B1...4 = [1, 0, 1, 0]. The cities and roads in Bazbesonin are shown in the following figure.

• The latency between city 1 and city 2 is 1.
• The latency between city 1 and city 3 is 2.
• The latency between city 1 and city 4 is 1.
• The latency between city 1 and city 5 is 2.
• The latency between city 2 and city 3 is 1.
• The latency between city 2 and city 4 is 1.
• The latency between city 2 and city 5 is 2.
• The latency between city 3 and city 4 is 1.
• The latency between city 3 and city 5 is 2.
• The latency between city 4 and city 5 is 1.

Therefore, the bottleneck in this example is 2.

The input begins with a line containing a single integer N (2 ≤ N ≤ 100 000), the number of cities in Bazbesonin. The next line contains N − 1 integers Ei (Ei ∈ {0, 1}) representing the economic condition of Bazbesonin.

Output a single integer on one line, the bottleneck of the message exchange.