#include<bits/stdc++.h>
using namespace std;

// 二叉树 数据结构
struct TreeNode{
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int val,TreeNode *left = nullptr,TreeNode *right = nullptr){
      val = val;
      left = left;
      right = right;
  }
};

// 根据 层序 遍历 创建 二叉树
int n;
TreeNode* create(int arr[],int u){
    if(u > n) return nullptr;
    if(arr[u] == -1) return nullptr;
    TreeNode *root = new TreeNode(arr[u]);
    root->val = arr[u];
    root->left = create(arr,2 * u);
    root->right = create(arr,2 * u + 1);
    return root;
}

vector<int> pre;
vector<int> npre;

//递归写法 前序遍历
void preorder(TreeNode *root)
{
    if(root == nullptr) return ;
    pre.push_back(root->val);
    preorder(root->left);
    preorder(root->right);
}

typedef pair<TreeNode *,char> pic;
// 非递归写法 前序遍历
void nPre(TreeNode *root){
    if(root == nullptr) return ;
    stack<pic> stk;
    stk.push({root,'r'});
    while(stk.size())
    {
        auto t = stk.top();
        stk.pop();

        if(t.first != nullptr)
        {
            if(t.second == 'b') npre.push_back(t.first->val);
            else{
                stk.push({t.first->right,'r'});
                stk.push({t.first->left,'r'});
                stk.push({t.first,'b'});
                //stk.push({t.first,'b'}) 放在最后是前序遍历，中间是中序，最上是后序
            }
        }
    }
    return;
}

int main()
{
    cin >> n;

    //层序遍历，输入数组，从数组建树
    int arr[n];
    for(int i = 1;i <= n;i++) cin >> arr[i];
    auto root = create(arr,1);

    preorder(root);
    for(auto &x:pre) cout << x << " ";
    cout << endl;
    nPre(root);
    for(auto &x:npre) cout << x << " ";
}