/*
Data: 2019-06-24 15:36:45
Problem: PAT_A1123#Is It a Complete AVL Tree
AC: 35:46
题目大意：
由插入序列构造一棵AVL树，输出层次遍历并判断是否为一棵完全二叉树
基本思路：
构造平衡二叉树，
中序遍历并判断是否为完全二叉树
*/
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
struct node
{
int data;
int height;
node *lchild, *rchild;
};
int GetHeight(node *root)
{
if(root == NULL)
return ;
else
return root->height;
}
int GetBalanceFactor(node *root)
{
return GetHeight(root->lchild) - GetHeight(root->rchild);
}
void UpdataHeight(node *&root)
{
root->height = max(GetHeight(root->lchild),GetHeight(root->rchild))+;
}
void LeftRotation(node *&root)
{
node *temp = root->rchild;
root->rchild = temp->lchild;
temp->lchild = root;
UpdataHeight(root);
UpdataHeight(temp);
root = temp;
}
void RightRotation(node *&root)
{
node *temp = root->lchild;
root->lchild = temp->rchild;
temp->rchild = root;
UpdataHeight(root);
UpdataHeight(temp);
root = temp;
}
void Insert(node *&root, int x)
{
if(root == NULL)
{
root = new node;
root->data = x;
root->height=;
root->lchild = root->rchild = NULL;
}
else if(x < root->data)
{
Insert(root->lchild, x);
UpdataHeight(root);
if(GetBalanceFactor(root) == )
{
if(GetBalanceFactor(root->lchild) == )
RightRotation(root);
else
{
LeftRotation(root->lchild);
RightRotation(root);
}
}
}
else
{
Insert(root->rchild, x);
UpdataHeight(root);
if(GetBalanceFactor(root) == -)
{
if(GetBalanceFactor(root->rchild) == -)
LeftRotation(root);
else
{
RightRotation(root->rchild);
LeftRotation(root);
}
}
}
}
int IsComplete(node *root, int n)
{
queue<node*> q;
q.push(root);
int cnt=, ans=;
while(!q.empty())
{
root = q.front();
q.pop();
if(root)
{
printf("%d%c", root->data,++cnt==n?'\n':' ');
q.push(root->lchild);
q.push(root->rchild);
}
else
{
if(cnt==n)
break;
else
{
ans=;
while(!q.empty())
{
root = q.front();
if(root) break;
else q.pop();
}
}
}
}
return ans;
}
int main()
{
#ifdef ONLINE_JUDGE
#else
freopen("Test.txt", "r", stdin);
#endif // ONLINE_JUDGE
int n,x;
node *root = NULL;
scanf("%d", &n);
for(int i=; i<n; i++)
{
scanf("%d", &x);
Insert(root, x);
}
if(IsComplete(root, n))
printf("YES");
else
printf("NO");
return ;
}