小红有一个长度为 n 的排列 p,其中 1 到 n 的每个数都恰好出现一次,pos[i] 表示排列中元素 i 的下标。例如 p = [3,2,4,5,1],则 pos = [5,2,1,3,4]。还有一个长度为 m 的数组 a,数组的元素互不相同,即 ai != aj,如果满足 pos[a[i]] < pos[a[i+1]] <= pos[a[i]] + d,则认为 a 是一个优秀的数组。
现在给定长度为 n 的排列 p,以及长度为 m 的数组a1, a2, ... am,小红想知道最少需要多少次操作可以将数组变的不优秀,每次操作可以交换排列 p 的相邻元素,对应的 pos 数组也会发生变化。
输入描述
一行三个整数 n, m, d(2 <= m <= n <= 10^5), 表示排列的长度, 数组的长度以及 d 的值。
一行 n 个整数 p1, p2, ..., pn,表示排列 p。一行 m 个整数 a1, a2, ..., am,表示数组 a。
输出描述
输出一个整数表示最少需要多少次操作。
输入示例
5 2 2
3 2 4 5 1
3 4
输出示例
1
提示信息
只需要交换 4,5 得到 p = [3,2,5,4,1], 这样 a = [3,4] 就不是优秀数组了。