#include <iostream>
using namespace std;
struct
node
{
int n;
int lf, rt;
node()
{
n = lf = rt = -1;
}
}tree[1001];
void
__readandinit__();
void
__searchandins__(int n, int subscr, int nsubscr);
void
visitP(node x);
void
visitM(node x);
void
visitA(node x);
int
main()
{
__readandinit__();
visitP(tree[1]); cout << endl;
visitM(tree[1]); cout << endl;
visitA(tree[1]); cout << endl;
return 0;
}
void
__readandinit__()
{
int HowManyNodes;
cin >> HowManyNodes >> tree[1].n;
for(int i = 2; i <= HowManyNodes; i++)
{
cin >> tree[i].n;
__searchandins__(tree[i].n, 1, i);
}
}
void
visitP(node x)
{
if(x.n != -1)
cout << x.n << " ";
if(x.lf != -1)
visitP(tree[x.lf]);
if(x.rt != -1)
visitP(tree[x.rt]);
}
void
visitM(node x)
{
if(x.lf != -1)
visitM(tree[x.lf]);
if(x.n != -1)
cout << x.n << " ";
if(x.rt != -1)
visitM(tree[x.rt]);
}
void
visitA(node x)
{
if(x.lf != -1)
visitA(tree[x.lf]);
if(x.rt != -1)
visitA(tree[x.rt]);
if(x.n != -1)
cout << x.n << " ";
}
void
__searchandins__(int n, int subscr, int nsubscr)
{
if(n < tree[subscr].n)
{
if(tree[subscr].lf == -1)
tree[subscr].lf = nsubscr;
else
__searchandins__(n, tree[subscr].lf, nsubscr);
}
else
{
if(tree[subscr].rt == -1)
tree[subscr].rt = nsubscr;
else
__searchandins__(n, tree[subscr].rt, nsubscr);
}
}