Recover Tree Preorder

Interview

Time limit5sMemory limit128 MB

Summary

Given a tree's inorder and postorder sequences, reconstruct the tree and output its preorder traversal.

Level: Medium5 of 10
Topics: Tree, Recursion, Divide and conquer
Solved: No attempts yet

Problem

A binary tree has n vertices labeled with distinct integers from 1 to n. You are given the tree's inorder traversal and postorder traversal. Print the preorder traversal of the same tree.

Input

The first line contains n (1 <= n <= 100,000), the number of vertices.

The second line contains n integers, the inorder traversal.

The third line contains n integers, the postorder traversal of the same tree.

Output

Print the preorder traversal on one line, with values separated by spaces.

Examples1

Example 1
Input
```
3
1 2 3
1 3 2
```
Expected output
```
2 1 3
```