#include<queue>

void median(vector<int> arr,int n,vector<int> &ans)

{

  priority_queue<int> maxheap,minheap;

  for(int i=0;i<n;i++)

  {

    maxheap.push(arr[i]);

    int temp=maxheap.top();

    maxheap.pop();

    minheap.push(-1* temp);

    if(minheap.size() > maxheap.size())

    {

        int temp=minheap.top();

        minheap.pop();

        maxheap.push(-1 * temp);

    }

    if(maxheap.size() != minheap.size())

    {

        ans.push_back(maxheap.top());

    }

    else

    {

        ans.push_back((maxheap.top() * 1 - minheap.top() * 1) / 2);

    }

  }

}

vector<int> findMedian(vector<int> &arr, int n)

{

  vector<int> ans;

  median(arr,n,ans);

  return ans;

}

BinaryTreeNode<int>* PreorderToBST(vector<int> &preorder,int max,int &i)

{

   if(i >=preorder.size())

   {

       return NULL;

   }

   if (preorder[i] > max) {

       return NULL;

   }

   BinaryTreeNode<int> *Temp = new BinaryTreeNode<int>(preorder[i++]);

   Temp->left=PreorderToBST(preorder,Temp->data,i);

   Temp->right=PreorderToBST(preorder,max,i);

   return Temp;

}

BinaryTreeNode<int>* preorderToBST(vector<int> &preorder) {

    // Write your code here.

    int max=INT_MAX;

    int i=0;

    return PreorderToBST(preorder,max,i);

}

void inorder(TreeNode<int>* root,vector<int> &ans)

{  

    if(root==NULL)

    {

        return ;

    }

    inorder(root->left,ans);

    ans.push_back(root->data);

    inorder(root->right,ans);

}

TreeNode<int>* flatten(TreeNode<int>* root)

{

    // Write your code here

    vector<int>  ans; 

    inorder(root,ans);

    TreeNode<int>* newroot=new TreeNode<int>(ans[0]);

    TreeNode<int>* head=newroot;

    for(int i=1;i<ans.size();i++)

    {

         TreeNode<int>* temp= new TreeNode<int>(ans[i]);

         head->left=NULL;

         head->right=temp;

         head=temp;

    }

    head->left=NULL;

    head->right=NULL;

    return newroot;

}