Code: Move Back at a Cost

#include <bits/stdc++.h>
using namespace std;

void solve(vector<int> &a) {
    int n = a.size();

    vector<int> suff(n);
    // suff[i] denotes the index of minimum element in the suffix a[i...n-1]
    // In case of ties, the leftmost occurence is considered.

    suff[n - 1] = n - 1;
    for (int i = n - 2; i >= 0; i--) {
        if (a[i] <= a[suff[i + 1]]) {
            suff[i] = i;
        } else {
            suff[i] = suff[i + 1];
        }
    }

    vector<int> ans;
    multiset<int> remain;
    int R = suff[0];
    ans.push_back(a[R]);

    for (int i = 0; i < R; i++) {
        remain.insert(a[i] + 1);
    }
    while (R < n - 1) {
        int rhs_minima = a[suff[R + 1]];
        int lhs_minima = INT_MAX;
        if (!remain.empty()) {
            lhs_minima = *remain.begin();
        }

        if (lhs_minima < rhs_minima) {
            for (int i = R + 1; i < n; i++) {
                remain.insert(a[i] + 1);
            }
            break;
        } else {
            for (int i = R + 1; i < suff[R + 1]; i++) {
                remain.insert(a[i] + 1);
            }
            ans.push_back(rhs_minima);
            R = suff[R + 1];
        }
    }

    for (int ele : remain) {
        ans.push_back(ele);
    }

    for (int &ele : ans) {
        cout << ele << " ";
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        solve(a);
    }
    return 0;
}

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

constexpr int inf = 1E9;

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    std::vector<int> stk, b;
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && a[i] < stk.back()) {
            b.push_back(stk.back() + 1);
            stk.pop_back();
        }
        stk.push_back(a[i]);
    }

    std::sort(b.begin(), b.end());

    while (!b.empty() && stk.back() > b[0]) {
        b.push_back(stk.back() + 1);
        stk.pop_back();
    }

    std::sort(b.begin(), b.end());

    a = stk;
    for (auto x : b) {
        a.push_back(x);
    }

    for (int i = 0; i < n; i++) {
        std::cout << a[i] << " \n"[i == n - 1];
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}