站外题求助

【问题描述】
众所周知，熟练掌握至少一种排序算法是参加NOIP的必备技能。常见的排序算法有冒泡排序、归并排序、快速排序、奇偶排序、猴子排序、梳排序、鸡尾酒排序、臭皮匠排序等。

在这里，介绍一种利用栈进行排序的方法。例如，当数组中的元素为 1，3，2 时，我们可以利用栈对其进行排序：1 入栈；3 入栈；3 出栈；2 入栈；2 出栈；1 出栈。在这个例子中，出栈序列是 3，2，1，因而实现了对数组的排序。

遗憾的是，在不打乱入栈顺序的前提下，有时仅仅借助一个栈是不能实现对数组的完全排序。例如给定数组 2，1，3，借助一个栈，能获得的字典序最大的出栈序列是 3，1，2。（2 入栈；1 入栈；3 入栈；3 出栈；1 出栈；2 出栈）

现请你借助一个栈，在不打乱入栈顺序的情况下，对数组进行从大到小排序。当无法完全排序时，请输出字典序最大的出栈序列。

【输入格式】
输入共 2 行。

第一行包含一个正整数 n，表示入栈序列长度。

第二行包含 n 个整数，表示入栈序列。输入数据保证给定的序列是 1 到 n 的全排列，即不会出现重复数字。

【输出格式】
输出仅一行，共 n 个整数，表示字典序最大的出栈序列。

【样例输入1】
5
2 1 5 3 4

【样例输出1】
5 4 3 1 2

【样例解释1】
2入栈；1入栈；5入栈；5出栈；3入栈；4入栈；4出栈；3出栈；1出栈；2出栈

【数据范围及约定】

对于100%的数据：N ≤ 1000000。

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

const int N = 100005, M = 1000105;
int n, a[M], b[M], cnt, mx[M];
stack<int> s;

signed main(){
	//	freopen("sort.in", "r", stdin);
	//	freopen("sort.out", "w", stdout);
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
	for (int i = n; i >= 1; i--) mx[i] = max(mx[i + 1], a[i]);
	for (int i = 1; i <= n; i++){
		if (i == 1){
			s.push(a[1]);
			continue;
		}
		if (a[i] != mx[i]) s.push(a[i]);
		else b[++cnt] = a[i];
	}
	while(!s.empty()){
		b[++cnt] = s.top();
		s.pop();
	}
	for (int i = 1; i <= cnt; i++) printf("%lld ", b[i]);
	return 0;
}