如果规定只能使用一个栈作为存储结构对序列进行排序是否存在这样的算法又是否对所有的序列都适用这就是栈可排序排列Stack-sortable permutation问题。著名理论计算机科学家高德纳Kunth在 1968 年提出了以下算法解决这一问题初始化一个空栈对于每个输入值 xx当栈非空且 xx 大于栈顶元素时将栈中的元素弹出到输出端。将 xx 压入栈中只要栈不为空就将栈中元素弹出至输出端。高德纳注意到并非所有序列在使用该算法后都能被排序能够被排序的序列需要满足一定的条件。小 A 在阅读完这些资料后很感兴趣想进一步进行探究因此他打算先完成第一步的工作即尝试实现高德纳的算法但他不太确定这个算法到底要使用多少栈空间。请问对于给定的序列按以上算法执行最少需要的栈空间是多少并请给出第一次栈空间被使用满时的栈的布局。输入格式:输入第一行是一个正整数 NN (1≤N≤1051≤N≤105)表示输入序列长度。接下来的一行是 NN 个小于 106106 的正整数用一个空格隔开表示输入序列。输出格式:输出第一行是一个正整数表示最少需要的栈空间。接下来的一行是若干个正整数用一个空格隔开表示第一次栈空间被使用满时的栈的布局输出时从栈顶到栈底输出。输入样例:10 2 5 10 3 4 1 7 9 6 8输出样例:3 1 4 10#include bits/stdc.h using namespace std; vectorlong long v; int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); long long cnt0; int n;cinn; stacklong long st,ans; for(int i0;in;i){ long long k;cink; if(st.empty()){ st.push(k); }else{ if(kst.top()){ while(!st.empty()kst.top()){ st.pop(); } st.push(k); }else st.push(k); } int lst.size(); if(lcnt){ cntl; ansst; } } coutcntendl; long long y; if(!ans.empty()){ yans.top(); ans.pop(); couty; } while(!ans.empty()){ yans.top(); ans.pop(); cout y; } coutendl; return 0; }