给定一棵二叉树，判断其是否是AVL树（平衡二叉树），如果不是AVL树的话，输出"NOT AVL TREE!!!“以及不平衡的结点个数；否则判断其是否是一棵完全二叉树，如果不是完全二叉树的话，输出"NOT COMPLETE TREE!!!” 以及结点个数饱和的最后一层层号（假设根结点层号为1，且第i层的结点个数饱和是指该层的结点个数等于2^(i-1)）；否则将这棵完全二叉树经过若干次向下调整变成大顶堆，输出"OHHHHH HEAP!!!"以及此过程中将父结点与子结点交换的总次数（每次父结点与子结点交换都算一次，即同一轮向下调整的过程中可能有多次交换）。

Input

每个输入文件中一组数据。
第一行一个正整数N（N<=20），代表二叉树的结点个数（结点编号为1到N）。
第二行按结点编号从小到大的顺序给出N个结点的权值（各结点的权值均小于20且各不相同）。
接下来按结点编号从小到大的顺序给出N行，每行为两个编号，分别代表该结点的左孩子编号和右孩子编号，
如果不存在左(右)孩子，那么就用字符'-'代替。数据保证编号在1到N之间。

Output

分两行按题目描述中的字符串和相应统计结果。

Sample Input

5
1 2 3 4 5
2 3
4 5
- -
- -
- -

Sample Output

OHHHHH HEAP!!!
3

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005,MAXM=105;
int n;
int hight[MAXN],ans_heap,root,sum[MAXM],max_hight,ans_AVL,mp[MAXN],ans_com;
char sbuf[MAXN];
struct node
{
    long long val;
    int ch[2];
}t[MAXN];
bool is_root[MAXN];
void dfs(int root,int deep,int pos)
{
    sum[deep]++;
    mp[pos]=root;
    if(t[root].ch[0])
    {
        dfs(t[root].ch[0],deep+1,pos*2);
    }
    if(t[root].ch[1])
    {
        dfs(t[root].ch[1],deep+1,pos*2+1);
    }
    max_hight=max(deep,max_hight);
    hight[root]=max(hight[t[root].ch[0]],hight[t[root].ch[1]])+1;
}
bool ck_AVL()
{
    ans_AVL=0;
    for(int i=1;i<=n;++i)
    {
        if(abs(hight[t[i].ch[0]]-hight[t[i].ch[1]])>1)
        {
            ++ans_AVL;
        }
    }
    return ans_AVL==0;
}
bool ck_COM()
{
    for(int i=1;i<=max_hight;++i)
    {
        if(sum[i]==(1<<(i-1)))ans_com=i;
    }
    for(int i=1;i<=n;++i)
    {
        if(!mp[i])return false;
    }
    return true;
}
bool ck_HEAP()
{
    for(int i=1;i<=n;++i)
    {
        if(t[i].ch[0])
        {
            if(t[i].val<t[t[i].ch[0]].val)return false;
        }
        if(t[i].ch[1])
        {
            if(t[i].val<t[t[i].ch[1]].val)return false;
        }
    }
    return true;
}
void go()
{
    for(int i=(n>>1);i;--i)
    {
        int now_node=mp[i];
        int now=i;
        while((now<<1)<=n)
        {
            int ch_node;
            int ch;
            if((now<<1)+1<=n)
            {
                ch_node=t[mp[(now<<1)]].val>t[mp[(now<<1)+1]].val?mp[(now<<1)]:mp[(now<<1)+1];
                ch=t[mp[(now<<1)]].val>t[mp[(now<<1)+1]].val?(now<<1):(now<<1)+1;
            }
            else
            {
                ch_node=mp[(now<<1)];
                ch=(now<<1);
            }
            if(t[now_node].val<t[ch_node].val)
            {
                swap(t[now_node].val,t[ch_node].val);
                now_node=ch_node;
                now=ch;
                ++ans_heap;
            }
            else
            {
                break;
            }
        }
    }
    return;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        memset(t,0,sizeof(node)*(n+1));
        for(int i=1;i<=n;++i)
        {
            scanf("%lld",&t[i].val);
            is_root[i]=true;
            mp[i]=0;
        }
        for(int i=1;i<=n;++i)
        {
            scanf("%s",sbuf);
            if(*sbuf!='-')
            {
                sscanf(sbuf,"%d",&t[i].ch[0]);
            }
            scanf("%s",sbuf);
            if(*sbuf!='-')
            {
                sscanf(sbuf,"%d",&t[i].ch[1]);
            }
            is_root[t[i].ch[0]]=is_root[t[i].ch[1]]=false;
        }
        for(int i=1;i<=n;++i)
        {
            if(is_root[i])
            {
                root=i;
                break;
            }
        }
        dfs(root,1,1);
        if(!ck_AVL())
        {
            printf("NOT AVL TREE!!!\n");
            printf("%d\n",ans_AVL);
            continue;
        }
        if(!ck_COM())
        {
            printf("NOT COMPLETE TREE!!!\n");
            printf("%d\n",ans_com);
            continue;
        }
        ans_heap=0;
        go();
        printf("OHHHHH HEAP!!!\n");
        printf("%d\n",ans_heap);

    }
    return 0;
}