Day3-F-Buy Low Sell High-CodeForces867E

You can perfectly predict the price of a certain stock for the next N days. You would like to profit on this knowledge, but only want to transact one share of stock per day. That is, each day you will either buy one share, sell one share, or do nothing. Initially you own zero shares, and you cannot sell shares when you don't own any. At the end of the N days you would like to again own zero shares, but want to have as much money as possible.

Input

Input begins with an integer N (2 ≤ N ≤ 3·10⁵), the number of days.

Following this is a line with exactly N integers p₁, p₂, ..., p_N (1 ≤ p_i ≤ 10⁶). The price of one share of stock on the i-th day is given by p_i.

Output

Print the maximum amount of money you can end up with at the end of N days.

Examples

Input

9
10 5 4 7 9 12 6 2 10

Output

Input

20
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4

Output

Note

In the first example, buy a share at 5, buy another at 4, sell one at 9 and another at 12. Then buy at 2 and sell at 10. The total profit is - 5 - 4 + 9 + 12 - 2 + 10 = 20.

思路：依旧是贪心，维护一个优先队列，每次读取一个数与队顶判断，如果大于就出队并入队2次读取的数，答案加上差值，否则就入队一次。为什么要入队两次，因为有可能这次不应该卖，应该买，所以就需要入2次，例如：1 3 5 6，读取3时，答案加上2，这次应该是不卖而是买，入队2次，这样下次就是叠加上次的操作，5 - 3 + 3 - 1 == 5 - 1代码如下：

int n;

int main() {

    scanf("%d", &n);

    priority_queue<LL,vector<LL>,greater<LL>> q;

    LL sum = , now;

    scanf("%I64d", &now);

    q.push(now);

    for(int i = ; i < n; ++i) {

        scanf("%I64d", &now);

        if(now > q.top()) {

            sum += now - q.top();

            q.pop();

            q.push(now);

        }

        q.push(now);

    }

    printf("%I64d\n",sum);

    return ;

}

巴特西

Day3-F-Buy Low Sell High-CodeForces867E

最新文章

热门文章