31448번 - Ascending hike 다국어

문제

Participating in the Olympics requires training, e.g., climbing from deep valleys to high peaks. Hence, you decided to go out for a hike in which you would be continuously walking on an upward slope, with the largest possible elevation gain.

You have noted the altitude of several remarkable points through which your hike would go: these altitudes are pairwise distinct integers $A_1, A_2, \dots , A_N$. The slope between the $k$^th and $(k + 1)$^th remarkable points is upward if $A_k < A_{k+1},ドル and downward if $A_k > A_{k+1}$ . Given this list of altitudes, what is the maximal elevation gain of a continuously upward slope on your hike?

입력

The input consists of two lines. The first line contains the number $N$. The second line contains $N$ space-separated integers $A_1, A_2, \dots , A_N$.

출력

The output should contain a single line, consisting of a single number: the maximal integer $G$ for which there exist integers $k, k + 1, k + 2, \dots , \ell$ such that $A_k < A_{k+1} < A_{k+2} < \dots < A_{\ell} = A_k + G$.

제한

• 2ドル \le N \le 1,円 000,円 000$
• 0ドル \le A_k \le 1,円 000,円 000,円 000$ for all $k ⩽ N$

힌트