Search tree judgment (25 points)

For binary search trees , We stipulate that the left subtree of any node contains only the key values which are strictly smaller than the node , And its right subtree contains the key value greater than or equal to the node . If we swap the left and right subtrees of each node , The resulting tree is called a mirror binary search tree .

Now let's give a sequence of integer key values , Please write a program to judge whether the sequence is a preorder traversal sequence of a binary search tree or a mirror binary search tree , If it is , Then output the post order traversal sequence of the corresponding binary tree .

Input format :

The first line of input contains a positive integer N（≤1000）, The second line contains N It's an integer , For the given sequence of integer key values , Numbers are separated by spaces .

Output format :

The first line of the output first gives the judgment result , If the input sequence is the preorder traversal sequence of a binary search tree or a mirror binary search tree , The output YES, No side output NO. If it turns out that YES, The next line outputs the post order traversal sequence of the corresponding binary tree . Numbers are separated by spaces , But there can't be extra spaces at the end of the line .

sample input 1:

7
8 6 5 7 10 8 11

sample output 1:

YES
5 7 6 8 11 10 8

sample input 2:

7
8 6 8 5 10 9 11

sample output 2:

NO

#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;

int g[1010];
vector<int>kp;
int n;
bool f;
void build(int l,int r){
	if(l>r)return;
	int i=r,j=l+1;
	int t=g[l];
	if(f){
		while(g[i]>=t&&i>l)i--;
		while(g[j]<t&&j<=r)j++;
	}
	else {
		while(g[i]<t&&i>l)i--;
		while(g[j]>=t&&j<=r)j++;
	}
	if(j-i!=1)return;
	build(l+1,i);
	build(j,r);
	kp.push_back(t);
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>g[i];
	}
	build(0,n-1);
	if(kp.size()!=n){
		f=!f;
		build(0,n-1);
	}
	
	if(kp.size()==n){
		cout<<"YES\n";
		cout<<kp[0];
		for(int i=1;i<n;i++){
			cout<<" "<<kp[i];
		}
	}
	else cout<<"NO\n";
	return 0;
}