#include<stdio.h>
#define ERROR 0
#define OK 1
#define MAX_SIZE 100
#define N 100
typedef struct NODE{
    int arr[MAX_SIZE];
    int top;
}Node;
void init(Node &s){
   s.top = 0;
}
//壓棧
int pushElem(Node &s,int c){
   if(s.top == MAX_SIZE){
     return ERROR;//如果棧滿了，那么返回ERROR
   }
   s.arr[s.top++] = c;
   return OK;
}
//跳出棧頂元素
int popElem(Node &s,int &c){
   if(s.top == 0){
    /*
    如果棧為空，那么返回ERROR
    這里之所以是s.top == 0就為空，是因為下面進行刪除操作
    的時候s.top是先減減的，所以在s.top = 1的時候，先進行減1操作，所以
    這時候s.top已經(jīng)為0，表明我們已經(jīng)刪除了最后一個元素，再來進行這個操作的時候
    s.top為0，所以才用它來判斷棧是否為空
    */
     return ERROR;
   }
   c = s.arr[--s.top];//將刪除的元素賦值給c
   return OK;
}
//獲取棧頂元素
int getTop(Node &s,int &c){
    if(s.top == 0){
    /*
    如果棧為空，那么返回ERROR
    這里之所以是s.top == 0就為空，是因為下面進行刪除操作
    的時候s.top是先減減的，所以在s.top = 1的時候，先進行減1操作，所以
    這時候s.top已經(jīng)為0，表明我們已經(jīng)刪除了最后一個元素，再來進行這個操作的時候
    s.top為0，所以才用它來判斷棧是否為空
    */
     return ERROR;
   }
   c = s.arr[s.top - 1];//將棧頂元素賦值給c
   return OK;
}
int isEmpty(Node &s){
    return s.top == 0;
}
/*
將maxNum及其之前的數(shù)字壓入棧中，同時返回maxNum的下標(biāo)
*/
int getMax_index(int *arr,Node &s,int left,int right,int maxNum){
  int i;
  for(i = left; i < right; i++){
    pushElem(s,arr[i]);//將當(dāng)前的數(shù)字壓入棧中
    if(arr[i] == maxNum){
        //如果棧頂元素是最大值，那么就將退出循環(huán)遍歷
        break;
    }
  }
  return i;
}
/*
獲取left - right區(qū)間的最大值
*/
int arrayMax(int *arr,int left,int right){
  int i,maxNum = 0;
  for(i = left; i < right; i++){
    if(maxNum == 0 || arr[i] > maxNum)
        maxNum = arr[i];
  }
  return maxNum;
}
//獲取最大的出棧序列
void getMax(int *arr,Node &s,int  left,int right,int maxNum){
  if(left >= right){
  //如果區(qū)間的范圍不正確的時候，那么結(jié)束遞歸
     return;
  }
  //tmp表示棧頂元素，r_max表示maxNum后面子數(shù)組的最大值,i表示maxNum的下標(biāo)
  int i,tmp,r_max;
  /*
  將maxNum及它前面的數(shù)字壓入棧中，同時將maxNum的下標(biāo)返回
  */
  i = getMax_index(arr,s,left,right,maxNum);
  r_max = arrayMax(arr,i + 1,right);//獲取maxNum后面子數(shù)組的最大值
  /*
  這段代碼也可以不寫，因為下面會拿棧頂元素和r_max進行比較，所以
  maxNum是最大值，必然會先輸出manNum的
  popElem(s,tmp);//將最大值maxNum賦值給tmp，并從棧中跳出
  printf("%d ",tmp);
  */
  while(!isEmpty(s)){
        getTop(s,tmp);//獲取棧頂元素
        if(r_max > tmp){
           //判斷r_max是否大于棧頂元素，如果是，將它及其之前的數(shù)字壓入棧中，同時獲取r_max的下標(biāo)
            i = getMax_index(arr,s,i + 1,right,r_max);
            r_max = arrayMax(arr,i + 1,right);//獲取 i + 1 到right區(qū)間的最大值
           // printf("\n右邊最大值下標(biāo)為:%d\n",i);
        }else{
        //如果r_max小于等于棧頂元素，那么就將棧頂元素從棧中跳出，并將其輸出
           popElem(s,tmp);
           printf("%d ",tmp);
        }
  }
  getMax(arr,s,i + 1,right,r_max);
}
int main(){
  int arr[N];
  int n,i,maxNum;
  Node s;
  init(s);//初始棧
  printf("請輸入棧的元素個數(shù):");
  scanf("%d",&n);//輸入棧元素個數(shù)
  for(i = 0; i < n; i++)
    scanf("%d",&arr[i]);
  maxNum = arrayMax(arr,0,n);//獲取left-right區(qū)間的最大值
  getMax(arr,s,0,n,maxNum);
  return 0;
}