{"raw_statement":[{"iden":"statement","content":"Little Nastya has a hobby, she likes to remove some letters from word, to obtain another word. But it turns out to be pretty hard for her, because she is too young. Therefore, her brother Sergey always helps her.\n\nSergey gives Nastya the word _t_ and wants to get the word _p_ out of it. Nastya removes letters in a certain order (one after another, in this order strictly), which is specified by permutation of letters' indices of the word _t_: _a_1... _a_|_t_|. We denote the length of word _x_ as |_x_|. Note that after removing one letter, the indices of other letters don't change. For example, if _t_ = \"_nastya_\" and _a_ = \\[4, 1, 5, 3, 2, 6\\] then removals make the following sequence of words \"_nastya_\" \"_nastya_\" \"_nastya_\" \"_nastya_\" \"_nastya_\" \"_nastya_\" \"_nastya_\".\n\nSergey knows this permutation. His goal is to stop his sister at some point and continue removing by himself to get the word _p_. Since Nastya likes this activity, Sergey wants to stop her as late as possible. Your task is to determine, how many letters Nastya can remove before she will be stopped by Sergey.\n\nIt is guaranteed that the word _p_ can be obtained by removing the letters from word _t_."},{"iden":"input","content":"The first and second lines of the input contain the words _t_ and _p_, respectively. Words are composed of lowercase letters of the Latin alphabet (1 ≤ |_p_| < |_t_| ≤ 200 000). It is guaranteed that the word _p_ can be obtained by removing the letters from word _t_.\n\nNext line contains a permutation _a_1, _a_2, ..., _a_|_t_| of letter indices that specifies the order in which Nastya removes letters of _t_ (1 ≤ _a__i_ ≤ |_t_|, all _a__i_ are distinct)."},{"iden":"output","content":"Print a single integer number, the maximum number of letters that Nastya can remove."},{"iden":"examples","content":"Input\n\nababcba\nabb\n5 3 4 1 7 6 2\n\nOutput\n\n3\n\nInput\n\nbbbabb\nbb\n1 6 3 4 2 5\n\nOutput\n\n4"},{"iden":"note","content":"In the first sample test sequence of removing made by Nastya looks like this:\n\n\"_ababcba_\" \"_ababcba_\" \"_ababcba_\" \"_ababcba_\"\n\nNastya can not continue, because it is impossible to get word \"_abb_\" from word \"_ababcba_\".\n\nSo, Nastya will remove only three letters."}],"translated_statement":[{"iden":"statement","content":"小娜斯娅有一个爱好，她喜欢从一个单词中删除一些字母，以得到另一个单词。但她太年轻了，这项任务对她来说相当困难。因此，她的哥哥谢尔盖总是帮助她。\n\n谢尔盖给娜斯娅一个单词 #cf_span[t]，并希望从中得到单词 #cf_span[p]。娜斯娅按照特定顺序（逐个删除，顺序严格）删除字母，该顺序由单词 #cf_span[t] 的字母索引的排列 #cf_span[a1... a|t|] 指定。我们用 #cf_span[|x|] 表示单词 #cf_span[x] 的长度。注意，删除一个字母后，其他字母的索引不会改变。例如，如果 #cf_span[t = ]\"_nastya_\" 且 #cf_span[a = [4, 1, 5, 3, 2, 6]]，则删除操作会依次产生以下单词序列：\"_nastya_\" → \"_nastya_\" → \"_nastya_\" → \"_nastya_\" → \"_nastya_\" → \"_nastya_\" → \"_nastya_\"。\n\n谢尔盖知道这个排列。他的目标是在某个时刻阻止妹妹，然后自己继续删除，以得到单词 #cf_span[p]。由于娜斯娅喜欢这项活动，谢尔盖希望尽可能晚地阻止她。你的任务是确定娜斯娅在被谢尔盖阻止前最多能删除多少个字母。\n\n保证单词 #cf_span[p] 可以通过从单词 #cf_span[t] 中删除字母得到。\n\n输入的第一行和第二行分别包含单词 #cf_span[t] 和 #cf_span[p]。这些单词由拉丁字母的小写字母组成（#cf_span[1 ≤ |p| < |t| ≤ 200 000]）。保证单词 #cf_span[p] 可以通过从单词 #cf_span[t] 中删除字母得到。\n\n下一行包含一个排列 #cf_span[a1, a2, ..., a|t|]，表示娜斯娅删除单词 #cf_span[t] 中字母的顺序（#cf_span[1 ≤ ai ≤ |t|]，所有 #cf_span[ai] 互不相同）。\n\n请输出一个整数，表示娜斯娅最多能删除的字母数量。\n\n在第一个样例中，娜斯娅的删除序列如下：\n\n\"_ababcba_\" → \"_ababcba_\" → \"_ababcba_\" → \"_ababcba_\"\n\n娜斯娅无法继续，因为无法从单词 \"_ababcba_\" 中得到单词 \"_abb_\"。\n\n因此，娜斯娅只能删除三个字母。"},{"iden":"input","content":"输入的第一行和第二行分别包含单词 #cf_span[t] 和 #cf_span[p]。这些单词由拉丁字母的小写字母组成（#cf_span[1 ≤ |p| < |t| ≤ 200 000]）。保证单词 #cf_span[p] 可以通过从单词 #cf_span[t] 中删除字母得到。下一行包含一个排列 #cf_span[a1, a2, ..., a|t|]，表示娜斯娅删除单词 #cf_span[t] 中字母的顺序（#cf_span[1 ≤ ai ≤ |t|]，所有 #cf_span[ai] 互不相同）。"},{"iden":"output","content":"请输出一个整数，表示娜斯娅最多能删除的字母数量。"},{"iden":"examples","content":"输入\nababcba\nabb\n5 3 4 1 7 6 2\n输出\n3\n输入\nbbbabbbb\n1 6 3 4 2 5\n输出\n4"},{"iden":"note","content":"在第一个样例中，娜斯娅的删除序列如下：\"_ababcba_\" → \"_ababcba_\" → \"_ababcba_\" → \"_ababcba_\"。娜斯娅无法继续，因为无法从单词 \"_ababcba_\" 中得到单词 \"_abb_\"。因此，娜斯娅只能删除三个字母。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ t \\in \\Sigma^* $ be the initial word (alphabet $ \\Sigma = \\{a, b, \\dots, z\\} $).  \nLet $ p \\in \\Sigma^* $ be the target word, with $ |p| < |t| $.  \nLet $ A = (a_1, a_2, \\dots, a_{|t|}) $ be a permutation of $ \\{1, 2, \\dots, |t|\\} $, specifying the order of letter removals.\n\nLet $ t^{(k)} $ denote the word obtained after removing the first $ k $ letters according to $ A $, i.e., removing positions $ a_1, a_2, \\dots, a_k $ from $ t $.\n\n**Constraints**  \n1. $ 1 \\leq |p| < |t| \\leq 200{,}000 $  \n2. $ p $ is a subsequence of $ t $  \n3. $ A $ is a permutation of $ \\{1, 2, \\dots, |t|\\} $, all $ a_i $ distinct  \n\n**Objective**  \nFind the maximum $ k \\in \\{0, 1, \\dots, |t| - |p|\\} $ such that $ p $ is a subsequence of $ t^{(k)} $.","simple_statement":null,"has_page_source":false}