Description
You are given a preorder and a postorder traversal sequences.
Please tell me how many possible trees can be constructed from them.
Sample 1:
Preorder: 1 2 3
Postorder: 3 2 1
Sample 2:
Preorder: 3 1 2
Postorder: 1 2 3
Input
The first line contains an integer N, 1 <= N <= 30, representing that the possible binary trees consist of N nodes, each with a unique ID.
The second line contains N integers, giving the preorder traversal sequence.
The third line contains N integers, giving the postorder traversal sequence.
Limit:
Testcases 1~5 : N <= 10.
Testcases 6~9 : N <= 20.
Testcase 10 : N <= 30.
Output
Output the number of all possible binary trees that can be constructed from the given sequences.
Remember to add a new line in the end.