题目内容

小区门岗有一排取件挂钩，从左到右编号 $1 \sim n$。第 $i$ 个挂钩上的记录是整数 $a_i$：$a_i=0$ 表示空挂钩，$a_i\ge 1$ 表示挂着一张取件牌，取件牌上的数字表示包裹种类。

挂着取件牌的挂钩一共 $m$ 个，编号 $p_1,p_2,\ldots,p_m$ 严格递增。数据保证这些位置上的 $a_{p_j}\ge 1$，其余位置都是 $0$。只有这些取件牌算标记，种类就是 $a_{p_j}$。空挂钩不计入标记，上面的 $0$ 也不算一种包裹种类。

管理员要选一段连续挂钩 $[L,R]$（$1\le L\le R\le n$），同时满足下面两条：

• 这段里的取件牌恰好有 $K$ 张；
• 这 $K$ 张牌至少包含 $D$ 种不同的包裹种类。

区间长度是 $R-L+1$。空挂钩同样占长度。请输出最短长度。若不存在这样的区间，输出 $-1$。

输入描述

第一行四个整数 $n$、$m$、$K$、$D$。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

第三行 $m$ 个整数 $p_1,p_2,\ldots,p_m$。

约束

$1 \le n \le 10^5$

$1 \le m \le n$

$1 \le K \le m$

$1 \le D \le K$

$0 \le a_i \le 10^9$

$1 \le p_1 < p_2 < \cdots < p_m \le n$

$a_{p_j}\ge 1$，且 $i$ 不在 $p_1,\ldots,p_m$ 中时 $a_i=0$

输出描述

输出一个整数，为满足条件的最短区间长度。若不存在，输出 $-1$。

样例1

输入

11 5 3 2
0 1 1 0 2 1 0 0 0 0 3
2 3 5 6 11

输出

4

说明

取件牌在挂钩 $2,3,5,6,11$，种类依次是 $1,1,2,1,3$。区间内要恰好有 $3$ 张牌，且至少有 $2$ 种。

任意 $3$ 张牌如果在位置上不连续，中间就会夹着别的牌，张数会超过 $3$。所以只要检查从左到右连续的 $3$ 张牌，再把区间两端收到这 $3$ 张牌上：

• 牌在 $2,3,5$，种类为 $1,2$，共 $2$ 种。区间 $[2,5]$ 的长度是 $5-2+1=4$。挂钩 $4$ 是空的，不增加牌，也不增加种类。
• 牌在 $3,5,6$，种类为 $1,2,1$，共 $2$ 种。区间 $[3,6]$ 的长度是 $6-3+1=4$。
• 牌在 $5,6,11$，种类为 $2,1,3$，共 $3$ 种。区间 $[5,11]$ 的长度是 $11-5+1=7$。

三段都满足种类数，最短长度是 $4$。

区间 $[2,6]$ 含有 $4$ 张牌，张数不是 $3$，不能选。区间 $[1,5]$ 仍然只有挂钩 $2,3,5$ 这 $3$ 张牌，长度却是 $5$，比 $4$ 更长。

样例2

输入

8 5 3 3
5 5 0 6 0 0 6 7
1 2 4 7 8

输出

-1

说明

取件牌在 $1,2,4,7,8$，种类依次是 $5,5,6,6,7$。恰好 $3$ 张牌时，只能是下面三组连续的牌：

• 区间 $[1,4]$：牌在 $1,2,4$，种类为 $5,5,6$，只有 $2$ 种。挂钩 $3$ 上的 $0$ 是空位，不算种类。长度是 $4-1+1=4$。
• 区间 $[2,7]$：牌在 $2,4,7$，种类为 $5,6,6$，只有 $2$ 种。长度是 $7-2+1=6$。
• 区间 $[4,8]$：牌在 $4,7,8$，种类为 $6,6,7$，只有 $2$ 种。长度是 $8-4+1=5$。

三组的种类数都小于 $3$。

区间 $[1,8]$ 的种类是 $5,6,7$，有 $3$ 种，但取件牌有 $5$ 张，不是恰好 $3$ 张，不能选。因此没有合法区间，输出 $-1$。