小Nastya有一个爱好,她喜欢从单词中删除一些字母,以获得另一个单词。但事实证明这对她来说相当困难,因为她太年轻了。因此,她的哥哥谢尔盖总是帮助她。
Sergey 给 Nastya 单词 t,并想从中取出单词 p。 Nastya 按一定顺序删除字母(一个接一个,严格按照这个顺序),这是通过单词 t 的字母索引的排列来指定的:a1...a|t|。我们将单词 x 的长度表示为 |x|。请注意,删除一个字母后,其他字母的索引不会改变。例如,如果 t = "nastya" 且 a = [4, 1, 5, 3, 2, 6],则删除会生成以下单词序列 "nastya" $$\rightarrow$$ "nastya" $$\rightarrow$$ "nastya" $$\rightarrow$$ "nastya" $$\rightarrow$$ "nastya" $$\rightarrow$$ "nastya" $$\rightarrow$$ “娜斯佳”。
Sergey 知道这个排列。他的目标是在某个时候阻止他的妹妹,并继续自己移动以获得单词 p。由于 Nastya 喜欢这项活动,Sergey 希望尽可能晚地阻止她。你的任务是确定 Nastya 在被 Sergey 阻止之前可以删除多少个字母。
保证单词t去掉字母后可以得到单词p。
输入
输入的第一行和第二行分别包含单词 t 和 p。单词由拉丁字母的小写字母组成 (1 ≤ |p| < |t| ≤ 200 000)。保证通过去掉单词t中的字母可以得到单词p。
下一行包含排列 a1, a2, ..., a|t|字母索引的数量,指定 Nastya 删除 t 字母的顺序(1 ≤ ai ≤ |t|,所有 ai 都是不同的)。
输出
打印一个整数,即 Nastya 可以删除的最大字母数。
示例
输入 #1
ababcba abb 5 3 4 1 7 6 2
输出 #1
3
输入 #2
bbbabb bb 1 6 3 4 2 5
输出 #2
4
注意
在 Nastya 制作的第一个删除示例测试序列中,如下所示:
“ababcba”$$\rightarrow$$“ababcba”$$\rightarrow$$“ababcba”$$\rightarrow$$“ababcba”
Nastya 无法继续,因为不可能从单词“ababcba”中获取单词“abb”。
因此,Nastya 将仅删除三个字母。