#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
int min(int x, int y) { return x < y ? x : y; }
int max(int x, int y) { return x > y ? x : y; }
int maxProfit(int* prices, int pricesSize) {
int *dp
= malloc((pricesSize
+1)*sizeof(int)), ans
= 0; dp[pricesSize] = INT_MIN;
for (int i = pricesSize-1; i >= 0; --i)
dp[i] = max(dp[i+1],prices[i]);
for (int b = INT_MAX, i = 1; i < pricesSize; ++i)
b = min(b,prices[i-1]), ans = max(ans,dp[i] -= b);
return ans; }
int main(void) {
int *prices, pricesSize;
scanf("%d",&pricesSize
), prices
= malloc(pricesSize
*sizeof(int)); for (int i = 0; i < pricesSize; ++i)
printf("%d",maxProfit
(prices
,pricesSize
)), free(prices
); return 0; }
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0cmluZy5oPgojaW5jbHVkZSA8bGltaXRzLmg+CgppbnQgbWluKGludCB4LCBpbnQgeSkgeyByZXR1cm4geCA8IHkgPyB4IDogeTsgfQppbnQgbWF4KGludCB4LCBpbnQgeSkgeyByZXR1cm4geCA+IHkgPyB4IDogeTsgfQoKaW50IG1heFByb2ZpdChpbnQqIHByaWNlcywgaW50IHByaWNlc1NpemUpIHsKICAgIGludCAqZHAgPSBtYWxsb2MoKHByaWNlc1NpemUrMSkqc2l6ZW9mKGludCkpLCBhbnMgPSAwOwogICAgZHBbcHJpY2VzU2l6ZV0gPSBJTlRfTUlOOwoJZm9yIChpbnQgaSA9IHByaWNlc1NpemUtMTsgaSA+PSAwOyAtLWkpCgkJZHBbaV0gPSBtYXgoZHBbaSsxXSxwcmljZXNbaV0pOwogICAgZm9yIChpbnQgYiA9IElOVF9NQVgsIGkgPSAxOyBpIDwgcHJpY2VzU2l6ZTsgKytpKQogICAgCWIgPSBtaW4oYixwcmljZXNbaS0xXSksIGFucyA9IG1heChhbnMsZHBbaV0gLT0gYik7CiAgICBmcmVlKGRwKTsKICAgIHJldHVybiBhbnM7IH0KICAgIAppbnQgbWFpbih2b2lkKSB7CglpbnQgKnByaWNlcywgcHJpY2VzU2l6ZTsKCXNjYW5mKCIlZCIsJnByaWNlc1NpemUpLCBwcmljZXMgPSBtYWxsb2MocHJpY2VzU2l6ZSpzaXplb2YoaW50KSk7Cglmb3IgKGludCBpID0gMDsgaSA8IHByaWNlc1NpemU7ICsraSkKCQlzY2FuZigiJWQiLHByaWNlcytpKTsKCXByaW50ZigiJWQiLG1heFByb2ZpdChwcmljZXMscHJpY2VzU2l6ZSkpLCBmcmVlKHByaWNlcyk7CglyZXR1cm4gMDsgfQo=