题目描述
下面介绍一种新的匹配规则。
对于两个相互匹配的数列,其必须满足以下几个要求:
(1) 两个数列的长度相等。
(2) 两个数列中的第i大的数字的所在位置相同(若两个数字的大小相同,那么认为靠前的数字较小)。
例如,数列{1,3,1}和{4,8,5}相互匹配,
数列{1,4,9}和{5,4,7}不匹配。
现在给定一个长度为N的数列{A1,A2,…,An}和一个长度为M的模板数列{B1,B2,…,Bm}
求数列A中与模板数列B相匹配的子序列的个数(子序列可以部分重叠)。
数据规模
对于30%数据 N <= 1000 , M <= 30 ;
对于100%数据 N<=10000 , M <= 100 。
输入格式
第一行两个整数N,M
第二行N个整数,表示数列A
第三行M个整数,表示模板数列B
输出格式
一个整数,表示数列A中与模板数列B相匹配的子序列的个数。
样例输入
样例输出