교환 병목

시간 제한1초메모리 제한512 MB

요약

도시가 순서대로 세워지고, 새 도시는 이전의 모든 도시와 연결되거나 바로 앞 도시와만 연결될 때, 모든 도시 쌍의 최단 거리 중 최댓값을 구한다.

문제

바즈베소닌에는 현재 N개의 도시가 있으며, 1번부터 N번까지 번호가 붙어 있다. 두 도시 u와 v가 메시지를 교환할 때 지연 시간은 u에서 v로 이동하는 데 필요한 최소 도로 수로 정의한다.

이 도시들에는 오랜 역사가 있다. 처음에 바즈베소닌의 한가운데에 1번 도시가 세워졌다. 그 뒤 나머지 도시들이 2번부터 N번까지 차례대로 세워졌다. 도시 x를 세울 때, 그 당시 바즈베소닌의 경제 상황에 따라 하나 이상의 양방향 도로도 함께 세워졌다.

도시 x가 경제가 좋을 때 세워졌다면, 도시 x와 이전에 세워진 모든 도시를 잇는 도로가 세워졌다. 즉, 모든 1 ≤ y < x에 대해 도시 x와 도시 y를 잇는 도로가 세워졌다.
도시 x가 경제가 나쁠 때 세워졌다면, 도시 x와 도시 x − 1을 잇는 도로만 세워졌다.

바즈베소닌의 경제 상황은 이진 배열 E1...N−1로 나타낸다. 도시 x가 세워질 때 경제가 좋았다면 Ex−1의 값은 1이다. 그렇지 않으면 Ex−1의 값은 0이다.

현재에 이르러 N개의 도시 각각은 다른 모든 도시와 메시지를 교환하려 한다. 교환의 병목은 모든 도시 쌍 가운데 최대 지연 시간이다. 우리는 메시지 교환의 병목을 계산하려 한다.

예를 들어 N = 5이고 B1...4 = [1, 0, 1, 0]이라고 하자. 바즈베소닌의 도시와 도로는 다음 그림과 같다.

따라서 이 예에서 병목은 2이다.

입력은 정수 N (2 ≤ N ≤ 100 000) 하나를 포함한 줄로 시작한다. N은 바즈베소닌의 도시 수이다. 다음 줄에는 N − 1개의 정수 Ei (Ei ∈ {0, 1})가 주어지며, 바즈베소닌의 경제 상황을 나타낸다.

메시지 교환의 병목을 나타내는 정수를 한 줄에 출력한다.