34714번 - 경숲길 재개발 2

문제

서강대학교 인근 산책로인 경의선 숲길, 약칭 '경숲길'에는 $N$개의 건물이 일렬로 늘어선 도로가 있다. 하지만 이곳에 큰 문제가 발견되어 경숲길은 재개발에 착수했다.

경숲길에는 건물 옥상을 애용하는 사람이 많아 옥상은 항상 여가를 즐기는 사람들로 가득 찼다. 하지만 이곳에는 높이가 같은 건물이 너무 많아 다른 건물 옥상의 사람과 눈이 마주쳐 서로 어색해지는 상황이 빈번하게 일어났다!

이러한 불상사가 일어나지 않도록, 기존 건물을 일부 철거하고 다음과 같은 특별한 규칙에 따라 건물을 재설계하기로 했다. 일부 건물은 철거되지 않은 채 남아있다.

경숲길에 세워진 $N$개의 건물은 모두 양의 정수 높이 $H_i$를 가지며, 높이가 같은 두 건물 사이에는 반드시 그들보다 높이가 더 높은 건물이 존재해야 한다. 다시 말해, $H_i = H_j$ 를 만족하는 모든 $i,j (i<j)$에 대해, $i<k<j$ 이면서 $H_k > H_i$를 만족하는 $k$가 적어도 하나 존재해야 한다.

이러한 규칙에 맞도록 철거된 건물의 높이를 설계해야 하며, 철거되지 않은 건물의 높이는 변경할 수 없다. 여기서 특정 건물이 지나치게 높아지면 주변 경관을 해칠 수도 있기에, 가장 높은 건물의 높이가 최소가 되도록 해야 한다.

규칙에 맞도록 경숲길을 설계했을 때, 가장 높은 건물 높이의 최솟값을 구해보자.

입력

첫째 줄에 건물의 수 $N$이 주어진다. $(1 \leq N \leq 100,000円)$

둘째 줄에 각 건물의 높이 $H_i$가 공백을 사이에 두고 주어진다. $H_i$는 100ドル$보다 작거나 같은 음이 아닌 정수이며, 0ドル$이라면 그 건물은 철거된 건물, 즉 높이를 지정해야 하는 건물임을 의미한다. 새로 지정하는 높이에는 제한이 없다.

규칙에 맞게 건물 높이를 지정하는 것이 불가능한 입력은 주어지지 않는다.

출력

첫째 줄에 가장 높은 건물의 높이의 최솟값을 출력한다.

제한

노트