時間制限 : sec, メモリ制限 : KB
English / Japanese  

最大の利益

FX取引では、異なる国の通貨を交換することで為替差の利益を得ることができます。例えば、1ドル100円の時に 1000ドル買い、価格変動により 1ドル 108円になった時に売ると、(108円 $-$ 100円) $\times$ 1000ドル $=$ 8000円の利益を得ることができます。

ある通貨について、時刻 $t$ における価格 $R_t$ ($t = 0, 1, 2 ,,, n-1$)が入力として与えられるので、価格の差 $R_j - R_i$ (ただし、$j > i$ とする) の最大値を求めてください。

入力

最初の行に整数 $n$ が与えられます。続く $n$ 行に整数 $R_t$ ($t = 0, 1, 2 ,,, n-1$) が順番に与えられます。

出力

最大値を1行に出力してください。

制約

  • $ 2 \leq n \leq 200,000$
  • $ 1 \leq R_t \leq 10^9$

入力例 1

6
5
3
1
3
4
3

入力例 1 に対する出力

3

入力例 2

3
4
3
2

入力例 2 に対する出力

-1

Note

Algorithm