String Game
time limit per test 2 second memory limit per test 256 megabytes
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.

is specified by permutation of letters’ indices of the word t: a1… 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.

Sergey 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.

It is guaranteed that the word p can be obtained by removing the letters from word t.

传送门:CF779D

Input

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|≤200000). It is guaranteed that the word p can be obtained by removing the letters from word t. Next line contains a permutation a1,a2,...,a|t| of letter indices that specifies the order in which Nastya removes letters of t (1≤ai≤|t|, all ai are distinct).

Output

Print a single integer number, the maximum number of letters that Nastya can remove.

Sample Input

1
2
3
ababcba
abb
5 3 4 1 7 6 2

Sample Output

1
3

题解

比赛时又没做出来= = 其实是比较明显的二分,二分的是下面那个a数组,因为删去是从前到后有序的。 那么每次判断删到那个位置时,p串是否包含有t串(子序列),如果有就二分往后,没有就往前找 因为找的是操作步数最大的
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.io.*;  
import java.util.*;
public class Main {
static String t;
static String p;
static int[]index;
static boolean[]flag;
static int tlen;
static int plen;
public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
while(sc.hasNext()){
t=sc.next();
p=sc.next();
tlen=t.length();
index=new int[tlen];
flag=new boolean [tlen];
for(int i=0;i<tlen;i++) index[i]=sc.nextInt();

int start=0;
int end=tlen-1;
int mid=0;
while(start<end){
mid=(start+end+1)/2;
if(judge(mid)){
start=mid;
}
else{
end=mid-1;
}
}
pw.println(start);
pw.flush();
}

}
static boolean judge(int mid){
Arrays.fill(flag, true);
for(int i=0;i<mid;i++){
flag[index[i]-1]=false;
}
int count=0;
for(int i=0;i<t.length();i++){
if(flag[i]==true){
if(t.charAt(i)==p.charAt(count)){
count++;
}
if(count==p.length()) return true;
}
}
return false;
}
}