Editorial

Let $p_0,p_1,...,p_{n-1}$ be the stock prices over the days. Compute $d{p}_i=max(p_i,...,p_{n-1})$ — the maximum on the suffixes of the array $p$. If we buy a share at price $p_i$ on the $i$-th day, then in the future, we can profitably sell it at the highest price $d{p}_i$, gaining a profit of $d{p}_i-p_i$. We need to compute the total profit, which is equal to

Example

Let’s consider the second test. Compute the maximum on the suffixes of the array of stock prices.

For example, on the first day, we buy a share for $p_1=2$, and later sell it for $d{p}_1=9$ (the sale will occur on the third day).

The total profit will be $4+7+3+0+7+2+3+0+0=26$.

Algorithm realization

Read the input data.

scanf("%d", &n);
p.resize(n);
dp.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &p[i]);

Compute $d{p}_i=max(p_i,...,p_{n-1})$.

dp[n - 1] = p[n - 1];
for (i = n - 2; i >= 0; i--)
  dp[i] = max(p[i], dp[i + 1]);

Compute the total profit $res$. On the $i$-th day, we buy a share at price $p_i$, and later sell it for $d{p}_i$, gaining a profit of $d{p}_i-p_i$.

res = 0;
for (i = 0; i < n; i++)
  res = res + dp[i] - p[i];

Print the answer.

printf("%lld\n", res);

Python realization

Read the input data.

n = int(input())
p = list(map(int, input().split()))

Compute $d{p}_i=max(p_i,...,p_{n-1})$.

dp = [0] * n
dp[n - 1] = p[n - 1]
for i in range(n - 2, -1, -1):
  dp[i] = max(p[i], dp[i + 1])

Compute the total profit $res$. On the $i$-th day, we buy a share at price $p_i$, and later sell it for $d{p}_i$, gaining a profit of $d{p}_i-p_i$.

res = 0
for i in range(n):
  res += dp[i] - p[i]

Print the answer.

print(res)