题目描述

宇宙里一年一度的行星直线竞速赛正在进行中！！！ 此时，场上有n个行星位于一条无限长的直线上，按照从后到前的顺序给出这n个行星的速度：a1,a2,a3......an。

当后面的行星i超过前面的行星j时，会把前面的行星j撞碎，撞碎行星j会让当前行星i的速度减少aj，也就是说，ai = ai - aj。

在本题中，行星之间的距离保证如果在同一时间有多对行星即将发生碰撞，一定先让后面的行星碰撞。如6 4 1，一定让后面速度为6的行星先碰撞，具体实现可以理解为速度为6和4的行星之间的距离为2，而速度为4和1两个行星之间的距离为100

请按从后到前的顺序输出当行星不再发生碰撞时剩余行星的速度。

输入格式

第一行输入一个n表示行星数量。 第二行输入n个数，以空格间隔。

输出格式

在一行内按从后到前顺序输出剩余行星速度。

输入输出样例 #1

输入 #1

5
1 2 3 4 5

输出 #1

1 2 3 4 5

输入输出样例 #2

输入 #2

5
5 4 3 2 1

输出 #2

1 1 1

说明/提示

n < $10^5$

${\forall}$ $a_i$ < $10^{15}$

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<long long> v(n);
    for (int i=0;i<n;i++){
        cin>>v[i];
    }
    stack<long long> s;
    for (int i=n-1;i>=0;i--){
        if(!s.empty() && v[i]>s.top()){
            v[i] -= s.top();
            s.pop();
        }
        else{
            s.push(v[i]);
        }
    }
    while(!s.empty()){
        cout<<s.top()<<" ";
        s.pop();
    }
    return 0;
}