If stock \(i\) is bought, let \(a_i=1\).

If stock \(i\) is sold, let \(a_i=-1\).

If the stock \(i\) is neither bought nor sold, let \(a_i=0\).

Let \(s_i=a_1+a_2+...+a_n\).

Then \(s_i\ge 0(1\le i\le n)\) must be satisfied.

Initially, let all \(a_i\) be \(1\),that means buying all the stocks.And your profit is \(sum=- \sum_ {i=1}^np_i\).

Then we need to change some stocks from buying to selling, or neither buying nor selling.

Obviously, it’s best to find the most expensive one from all the stocks purchased and modify it. If there are multiple most expensive stocks, please choose the one on the far right. Assume that the stock that meets this condition is \(i\).

First, consider modifying \(a _i\) to \(- 1\),that is to change this stock from buying to selling.And your profit will change to \(sum=sum+2p_i\).

Then for \(i\le j\le n\)，\(s_j=s_j-2\),To ensure \(s_i\ge 0(1\le i\le n)\),\(min(s_i ,s_{i+1},...,s_n)\ge2\) must meet.

Second, consider modifying \(a _i\) to \(0\),that is to change this stock from buying to nothing.And your profit will change to \(sum=sum+p_i\).

Then for \(i\le j\le n\)，\(s_j=s_j-1\),To ensure \(s_i\ge 0(1\le i\le n)\),\(min(s_i ,s_{i+1},...,s_n)\ge1\) must meet.

Otherwise, we can’t modify it.

The above operations can be maintained with segment tree.

We continue to operate until we can do no more, and finally we get the sequence \(a\).

The answer is \(-\sum_{i=1}^n a_i*p_i\).

The time complexity of the algorithm is\(O(nlogn)\).

https://atcoder.jp/contests/abc250/submissions/31552768