행글라이더 조종사

위대한 행글라이더 조종사 Sigurður Jens가 Reykjavíkurborg에서 공연을 열려고 한다. 모두가 알다시피 Reykjavíkurborg에는 건물 한 줄만 있으며, 그 줄은 $n$개의 건물로 이루어져 있다. 따라서 Reykjavíkurborg를 $n$개의 정수로 이루어진 목록 $a_1, a_2, \dotsc, a_n$로 나타낼 수 있으며, 각 수 $a_i$는 $i$번째 건물의 높이를 미터 단위로 나타낸다. $i$번째 건물과 $j$번째 건물 사이의 거리는 단순히 수 $i$와 $j$의 차이이다(이는 $\mid i - j \mid$로도 쓸 수 있다).

모두가 알다시피 행글라이더 조종사 Sigurður Jens는 건물 사이를 활공하는 것으로 유명하다. 그는 매우 뛰어난 행글라이더 조종사이지만 출발 고도보다 더 높이 날아오를 수는 없다. 따라서 항상 활공을 시작한 높이보다 낮은 높이에 착륙해야 한다.

건물에 충돌할 가능성으로 인한 사고를 피하기 위해 Reykjavíkurborg는 그가 활공을 시작하는 건물과 활공을 끝내는 건물 사이의 모든 건물이 그 두 건물보다 낮아야 한다는 규칙을 정했다. 따라서 $a_i > a_j$이고 $i$과 $j$ 사이의 모든 건물이 $a_i$와 $a_j$보다 낮은 경우에만 두 건물 $i,j$ 사이를 활공할 수 있다고 할 수 있다.

Sigurður Jens는 Reykjavíkurborg에서의 공연이 가능한 한 흥미진진하기를 바라며, 활공의 흥미도는 활공이 가로지르는 거리로 정의된다. 따라서 그는 활공할 두 건물 중 가장 좋은 쌍을 찾아야 한다. 행글라이더 조종사 Sigurður Jens가 선보일 수 있는 모든 가능한 공연 중 그가 달성할 수 있는 최대 흥미도를 구하여라.

점수

그룹 | 점수 | 제한

1 | 20 | $1 \le n \le 100$, 모든 $a_i$는 서로 다름

2 | 25 | $1 \le n \le 5\,000$, 모든 $a_i$는 서로 다름

3 | 25 | $1 \le n \le 10^5$, $1 \le a_i \le 100$

4 | 30 | 추가 제한 없음

첫째 줄에 하나의 정수 $1 \le n \le 10^5$가 주어진다. 다음 줄에 공백으로 구분된 $n$개의 정수 $a_1, a_2, \dotsc, a_n$가 주어진다. 각 수 $a_i$에 대해 $1 \le a_i \le 10^9$가 성립한다.

공연에서 얻을 수 있는 최대 흥미도를 나타내는 하나의 정수를 출력한다. 가능한 공연이 없다면 $0$을 출력한다.