가장 좋은 전망

파리는 올림픽 기간에 관광객으로 붐빈다. 여러분은 도시를 벗어나 일직선 모양의 등산로를 걷고 싶다. 등산로의 매 킬로미터 지점(시작점과 끝점 포함)에는 이정표가 있고, 각 이정표에는 그 지점의 고도가 적혀 있다. 연속한 두 이정표 사이의 경사는 일정하며, 같은 고도를 가진 이정표는 없다.

어떤 지점의 경치 아름다움은, 여러분의 현재 위치와 등산 중에 지나온 위치 가운데 같은 고도였던 가장 가까운 이전 위치 사이의 거리(킬로미터)이다. 그런 이전 위치가 없으면 도시와 스모그가 보인다는 뜻이므로 그 경치의 아름다움은 0이다.

이정표의 고도가 주어졌을 때, 등산 중 얻을 수 있는 가장 큰 아름다움을 구하라.

첫째 줄에 이정표의 개수 $N$이 주어진다. 둘째 줄에는 $N$개의 정수 $H_1, H_2, \dots, H_N$이 공백으로 구분되어 주어지며, $H_k$는 $k$번째 이정표의 고도이다.

가장 큰 아름다움 점수 $S$를 한 줄에 출력한다. $S$는 정수이거나, 기약분수 $N/D$($D \ge 2$, $\gcd(N, D) = 1$) 형태로 출력한다.

$1 \le N \le 100\,000$

모든 $k$에 대해 $0 \le H_k \le 1\,000\,000$

$H_k$는 서로 모두 다르다.