///*
// * tree04.cpp
// *
// *  Created on: Apr 13, 2024
// *      Author: 28032
// */
//#include  <bits/stdc++.h>
//#include <algorithm>
//
//using  namespace  std;
//
//class  heap
//{
//private:
//        int  n;
//        int  *elem;
//        void  shiftdown(int  pos)
//        {
//        	if (pos >= n) return;
//
//        	    int maxIndex = pos;
//        	    int leftIndex = 2 * pos + 1;
//        	    int rightIndex = 2 * pos + 2;
//
//        	    if (leftIndex < n && elem[leftIndex] > elem[maxIndex])
//        	    	maxIndex = leftIndex;
//
//        	    if (rightIndex < n && elem[rightIndex] > elem[maxIndex])
//        	    	maxIndex = rightIndex;
//
//        	    if (maxIndex != pos)
//        	    {
//        	        int t = elem[maxIndex];
//        	        elem[maxIndex] = elem[pos];
//        	        elem[pos] = t;
//        	        shiftdown(maxIndex);
//        	    }
//        }
//public:
//        heap(){}
//        heap(int  m)
//        {
//                n=m;
//                elem=new  int[n];
//        }
//        ~heap()
//        {
//                delete[]  elem;
//        }
//        void  initial()
//        {
//                for(int  i=0;  i<n;  i++)
//                        cin>>elem[i];
//        }
//
//        void  out()
//        {
//                for(int  i=0;  i<n;  i++)
//                {
//                        cout<<elem[i];
//                        if  (i<=n-2)
//                                cout<<"  ";
//                        else
//                                cout<<endl;
//                }
//        }
//
//        bool  isLeaf(int  pos)  const
//        {
//                return  ((pos>=n/2)  &&  pos<n);
//        }
//
//        int  leftChild(int  pos)
//        {
//                return  2*pos+1;
//        }
//
//        int  rightChild(int  pos)
//        {
//                return  2*pos+2;
//        }
//
//        void  arrange()
//        {
//                for(int  i=(n-1)/2;i>=0;  i--)
//                {
//                        shiftdown(i);
//                }
//        }
//
//        void  insertElem(int  x)
//        {
//        	int* elemt = new int[n+1];
//        	for(int i = 0;i < n;i++)
//        		elemt[i] = elem[i];
//
//        	elemt[n] = x;
//        	delete elem;
//        	elem = elemt;
//        	n++;
//
//        	arrange();
//        }
//};
//
//int  main()
//{
//        int  m;
//        cin>>m;
//        heap  *ex=new  heap(m);
//        ex->initial();
//        ex->arrange();
//        ex->out();
//        int  insData;
//        cin>>insData;
//        ex->insertElem(insData);
//        ex->out();
//        return  0;
//}
//
//
//