株の売買
お気に入りの会社の株価を表す
n 個の整数が与えられるとき、最適な買い時と売り時を決定したいと考えます。ただし、株は一度だけ買い、一度だけ売ることができます。そのため、安く買って高く売り、利益を最大化するのが目標です。このとき得られる最大利益を求めるプログラムを作成してください。もしどのように売買しても利益が得られない場合は、0 を出力してください（つまり、株を買わず売らずに終わるという意味です）。
入力
最初の行には整数
n (1 ≤ n ≤ ) が 1 つ与えられます。次の行には、株価を表す (0 ≤ ≤ 1000) が空白区切りで与えられます。
出力
買いと売りによって得られる最大利益を出力してください。
Examples
Input | Output |
5
4 2 6 8 1 | 6 |
4
8 6 4 3 | 0 |
解説
- 株価が 2 のときに買い、8 のときに売ることで最大利益が得られます。
- 株価が下がり続ける場合は利益を出せないので、0 を出力します。
Hint
各時点で、「これまでで最も安い株価」と「現在の最大利益」を同時に管理すると効率的に求められます。
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB