对于给定的一个二叉树的先序遍历和后序遍历，输出有多少种满足条件的二叉树。

两棵二叉树不同当且仅当对于某个x，x的左儿子编号不同或x的右儿子编号不同。

Input

第一行一个正整数n(3<=n<=10000)，表示二叉树的节点数，节点从1到n标号。第二行n个整数a[i](1<=a[i]<=n)，表示二叉树的先序遍历。第三行n个整数b[i](1<=b[i]<=n)，表示二叉树的后序遍历。

Output

输出一个整数表示有多少种方案。保证至少有1种方案。

Input示例

31 2 32 3 1

Output示例

1

---

统计出所有的可能（dfs遍历一次足矣），直接按照二叉树的性质，不过有个大数的运算

 

#include 
       
        #include 
        
         int pre[10005];int post[10005];int cc;void calc(int a1,int b1,int a2,int b2){    int i;    if(a1>=b1)  return;    for(i=a2; i<=b2-1; i++)    {        if(pre[a1+1] == post[i])  break;    }    if(i == b2-1)  cc++;    calc(a1+1,a1+1+(i-a2),a2,i);    calc(a1+1+(i-a2)+1,b1,i+1,b2-1);}int a[100000];int main(){    int n;    scanf("%d",&n);    for(int i=0; i
         
          =10)            {                a[i+1]=a[i+1]+a[i]/10;                if(i+1==sum)sum++;                a[i]=a[i]%10;            }    }    for(i=sum-1; i>=0; i--)        printf("%d",a[i]);    printf("\n");return 0;}