체중 감량

코지크는 다이어트를 결심했습니다. $n$일 동안 식단 관리와 고강도 운동을 이어갔지만, 체중은 매일 일정하게 줄어들지 않았고 때로는 (코지크 자신도 놀랍게) 오히려 늘어나기도 했습니다.

코지크는 매일 자신의 체중을 기록했습니다. 이제 친구들에게 자랑하기 위해, 기록 중에서 체중이 가장 많이 줄어든 연속 구간을 고르려고 합니다. 어떤 연속 구간에서 "줄어든 체중"이란 그 구간 첫날의 체중에서 마지막 날의 체중을 뺀 값입니다. 가능한 모든 연속 구간에 대해 이 값의 최댓값을 구하세요.

첫째 줄에 정수 $n$ ($1 \le n \le 3 \cdot 10^6$)이 주어집니다.

둘째 줄에 $n$개의 정수 $w_k$가 공백으로 구분되어 주어집니다. $w_k$는 다이어트 $k$일째 코지크의 체중이며 $1 \le w_k \le 10^9$입니다.

코지크의 최대 체중 감소량을 나타내는 정수 하나를 한 줄에 출력합니다.