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.

Sergey 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" $\rightarrow$ "nastya" $\rightarrow$ "nastya" $\rightarrow$ "nastya" $\rightarrow$ "nastya" $\rightarrow$ "nastya" $\rightarrow$ "nastya".

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.


-----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| ≤ 200 000). It is guaranteed that the word p can be obtained by removing the letters from word t.

Next 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).


-----Output-----

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


-----Examples-----
Input
ababcba
abb
5 3 4 1 7 6 2

Output
3
Input
bbbabb
bb
1 6 3 4 2 5

Output
4


-----Note-----

In the first sample test sequence of removing made by Nastya looks like this:

"ababcba" $\rightarrow$ "ababcba" $\rightarrow$ "ababcba" $\rightarrow$ "ababcba" 

Nastya can not continue, because it is impossible to get word "abb" from word "ababcba".

So, Nastya will remove only three letters.

Difficulty: competition

Starter code:

Solutions:
def sub(a, s):
    pa = 0
    ps = 0
    while pa < len(a) and ps < len(s):
        if a[pa] == s[ps]:
            ps += 1
            pa += 1
        else:
            pa += 1

    return ps == len(s)

def subword(t, ord_ar, n):
    t_copy = []
    for i in range(len(ord_ar)):
        if ord_ar[i] >= n:
            t_copy.append(t[i])
    return t_copy

def check(t, p, ord_ar, n):
    s = subword(t, ord_ar, n)
    return sub(s, p)

def bin_s(l, r, f):
    while r > l + 1:
        m = (r + l) // 2
        if f(m):
            l = m
        else:
            r = m
    return l



def main():
    t = input().strip()
    p = input().strip()
    ord_ar = [0]*len(t)
    
    seq = list(map(int, input().strip().split()))
    for i,x in enumerate(seq):
        ord_ar[x-1] = i

    ans = bin_s(0, len(t), lambda n: check(t, p, ord_ar, n))
    print(ans)

main()


def possible(t,p,a,n):
    s = ''
    check = [True]*len(t)
    for i in range(n):
        check[a[i]] = False
    for i in range(len(check)):
        if check[i]:
            s += t[i]
    
    m = len(s)
    lp = len(p)
    c = 0
    for i in range(m):
        if s[i] == p[c]:
            c += 1
        if c == lp:
            return True
    return False        
    
t = input()
p = input()
a = list(map(int,input().split()))
for i in range(len(a)):
    a[i] -= 1

low = 0
high = len(a)
ans = 0
while low <= high:
    mid = (low+high)//2
    if possible(t,p,a,mid):
        ans = mid
        low = mid+1
    else:
        high = mid-1
print(ans)        

   
t = input()
p = input()
a = [i-1 for i in list(map(int,input().split()))]
min1 = 0
max1 = len(t)
while(max1-min1)>1:
    med = min1+(max1-min1)//2
    j=0
    d=list(t)
    for i in range(med):
        d[a[i]]=''
    for i in range(len(t)):
        if d[i]==p[j]:
            j+=1
            if j==len(p):
                min1=med
                break
    if j!=len(p):
        max1=med
print(min1)



def main():
  a_string = input()
  b_string = input()
  moves = [int(x) for x in input().split()]
  index_of_move = {}
  lenb = len(b_string)

  for index, elem in enumerate(moves):
    index_of_move[elem] = index + 1

  l = 0
  r = len(moves) - 1
  while l < r:
    middle = int((l + r + 1) / 2)
    bi = 0
    i = 0

    for index, elem in enumerate(a_string):
      #if (index + 1) in moves[:(middle + 1)]:
      #  continue
      if index_of_move[index + 1] <= middle + 1:
        continue
      if elem is b_string[bi]:
        bi += 1
      if bi >= lenb:
        break

    if bi >= lenb:
      l = middle
    else:
      r = middle - 1

  if l is 0 and r is 0:
    bi = 0
    for index, elem in enumerate(a_string):
      if index_of_move[index + 1] <= 1:
        continue
      if elem is b_string[bi]:
        bi += 1
      if bi >= lenb:
        break
    if bi >= lenb:
      print(1)
    else:
      print(0)
  else:
    print(l + 1)

def __starting_point():
  main()

__starting_point()

#!/usr/bin/env python3
# -*- coding = 'utf-8' -*-

t = input()
p = input()
a = list(map(int, input().split()))

def can(s, p):
    i = 0
    for ch in s:
        if ch == p[i]:
            i += 1
            if i == len(p):
                return True

    return False

def binary_search(l, r):
    
    while(l < r - 1):
        s = list(t)
        mid = (l + r)//2

        for index in range(mid):
            s[a[index] - 1] = ' '
            
        ok = False
        i = 0
        for ch in s:
            if ch == p[i]:
                i += 1
                if i == len(p):
                    ok = True
                    break
        if ok:
            l = mid
        else:
            r = mid

    return l

print(binary_search(0, len(a) + 1))


a=input()
b=input()
c=[i-1 for i in list(map(int,input().split()))]
l=0
r=len(a)
while r-l>1:
    m=l+(r-l)//2
    t=list(a)
    j=0
    for i in range(m):t[c[i]]=''
    for i in range(len(a)):
        if t[i]==b[j]:
            j+=1
            if j==len(b):
                l=m;break
    if j!=len(b):r=m
print(l)


s = list(input().strip())
t = input().strip()
sq = [int(a) for a in input().strip().split()]
l = len(s)
lt = len(t)
def check(x):
    tmp = s.copy()
    for i in range(x):
        tmp[sq[i]-1] = '_'
    idx = 0
    for i in range(l):
        if tmp[i]==t[idx]:
            idx+=1
            if idx==lt:
                return True
    return False

low = res = 0
high = l
while(low<=high):
    mid = (low + high) >> 1
    if check(mid):
        low = mid + 1
        res = mid
    else:
        high = mid - 1
print(res)

s = list(input().strip())
t = input().strip()
sq = [int(a) for a in input().strip().split()]
l = len(s)
lt = len(t)
def check(x):
    tmp = s.copy()
    for i in range(x):
        tmp[sq[i]-1] = '_'
    idx = 0
    for i in range(l):
        if tmp[i]==t[idx]:
            idx+=1
            if idx==lt:
                return True
    return False

low = 0
high = l
while(low<=high):
    mid = (low + high) >> 1
    if check(mid):
        low = mid + 1
    else:
        high = mid - 1
print(high)

def is_subsequence(a, b, idx, top):
    i = 0
    for j, c in enumerate(a):
        if c == b[i] and idx[j+1] > top:
            i += 1
        if i == len(b):
            return True
    return False


a = input()
b = input()
r = list(map(int, input().split()))
idx = [0 for _ in range(len(r)+1)]
for i in range(len(r)):
    idx[r[i]] = i

lo = -1
hi = len(a)
while hi - lo > 1:
    mi = (lo + hi) // 2
    if is_subsequence(a, b, idx, mi):
        lo = mi
    else:
        hi = mi

print(lo+1)

#~ for i in range(-1, len(r)+1):
    #~ print(is_subsequence(a, b, idx, i))



import sys

# listindexes is sorted
def removeat(string, indexes):

    return [c for i, c in enumerate(string) if i not in indexes]

def contains(string, what):

    if not len(what):
        return True
    if not len(string):
        return False

    checked = 0
    for c in string:
        if what[checked] == c:
            checked += 1
            if checked == len(what):
                break

    return checked == len(what)

string = list(input())
what = list(input())
indexes = [i-1 for i in map(int, input().split())]

first = 0
last = len(indexes)-1

while first<last:

    midpoint = first + (last - first)//2 + (last - first)%2
    
    if contains(removeat(string, set(indexes[:midpoint])), what):
        first = midpoint
    else:
        last = midpoint-1

print(first)



import heapq
from bisect import bisect_left, bisect_right
from itertools import accumulate

def is_substr(fw, tw, seq):
    i, j = 0, 0
    while i < len(fw) and j < len(tw):
        if i in seq:
            i += 1
        elif fw[i] == tw[j]:
            i, j = i + 1, j + 1
        else:
            i += 1
    return j == len(tw)

R = lambda: map(int, input().split())
fw, tw = input(), input()
seq = [i - 1 for i in list(R())]
l, r = 0, len(seq) - 1
m, res = 0, 0
while l <= r:
    m = (l + r) // 2
    if is_substr(fw, tw, set(seq[:m])):
        res = max(res, m)
        l = m + 1
    else:
        r = m - 1
print(res)

def subseq (s,b):
  h = iter(b)
  return all(any(l == ch for l in h) for ch in s)

t = input()
p = input()
num = [int(x) for x in input().split()]
st = []
l = 0
r = len(num)
ans = r+1
while (l <= r):
  mid = (l+r)//2
  st = list(t)
  c = num[:mid]
  for i in c:
    st[i-1] = ''
  if subseq(p,''.join(st)):
    ans = mid
    l = mid + 1
  else:
    r = mid - 1
print(ans)

def main():
    s, w = ['', *input()], input()
    l = list(map(int, input().split()))
    lo, hi = 0, len(s) - len(w)
    while lo < hi:
        mid, t = (lo + hi) // 2, s[:]
        for i in l[:mid]:
            t[i] = ''
        try:
            i = 1
            for c in w:
                while c != t[i]:
                    i += 1
                i += 1
        except IndexError:
            hi = mid
        else:
            lo = mid + 1
    print(lo - 1)


def __starting_point():
    main()

__starting_point()

a=input()
b=input()
c=[i-1 for i in list(map(int,input().split()))]
l=0
r=len(a)
while r-l>1:
    m=l+(r-l)//2
    t=list(a)
    j=0
    for i in range(m):t[c[i]]=''
    for i in range(len(a)):
        if t[i]==b[j]:
            j+=1
            if j==len(b):
                l=m;break
    if j!=len(b):r=m
print(l)




# Made By Mostafa_Khaled


t = input()
p = input()

a = list(map(int, input().strip().split()))
a = [ x - 1 for x in a]
n = len(t)
m = len(p)


lo = 0
hi = n - 1

while lo < hi:
    mid = (lo + hi) >> 1
    
    temp = list(t)
    for x in a[ :mid+1]:
        temp[x] = '_'
    
    ptr, curr = 0, 0
    while ptr < n and curr < m:
        while ptr < n and temp[ptr] != p[curr]:
            ptr += 1
        if ptr < n:
            ptr += 1
            curr += 1
    
    if curr == m:
        lo = mid + 1
    else:
        hi = mid

print(lo)


t = list(input())
p = list(input())


def has_sub(temp):
    idx = 0
    for c in temp:
        if c == p[idx]:
            idx += 1
        if idx == len(p):
            return True

    return False


arr = list(map(int, input().split()))

left = 0
right = len(arr) - 1

while left < right:
    mid = (left + right + 1) // 2
    temp = t[:]

    for idx in range(mid):
        temp[arr[idx] - 1] = '0'

    if has_sub(temp):
        left = mid
    else:
        right = mid - 1

print(right)


t = input()
p = input()
ai = list(map(int,input().split()))
n = len(ai)
ti = [[t[i],1] for i in range(n)]
for i in range(n):
    ai[i] -= 1

num2 = 1

def check(num):
    nonlocal num2
    num2 -= 1
    for i in range(num):
        ti[ai[i]][1] = num2
    num3 = 0
    for i in ti:
        if i[1] == num2:
            continue
        if i[0] == p[num3]:
            num3 += 1
            if num3 == len(p):
                return True
    return False

high = n
low = 0
mid = (high + low) // 2
while high >= low:
    if check(mid):
        low = mid + 1
    else:
        high = mid - 1
    mid = (high + low) // 2

print(mid)


#print('HARE KRISHNA')
t=input()
p=input()
block=[int(i)-1 for i in input().split()]
ind={}
for i in range(len(block)):
    ind[block[i]]=i 
def is_part_and_parcel(s1,s2,mid):
    n=len(s2)
    m=len(s1)
    i=0 
    c=0 
    j=0 
    while i<n and j<m:
        if ind[j]<mid:
            j+=1 
            continue 
        if s2[i]==s1[j]:
            i+=1
            j+=1 
            c+=1 
        else:
            j+=1 
    return c==n 
n=len(t)
m=len(p)
lo= 0 
hi=len(block)-1 
while lo<=hi:
    mi=(lo+hi)>>1 
    if is_part_and_parcel(t,p,mi):
        ans=mi 
        lo=mi+1 
    else:
        hi=mi-1 
print(ans)

def is_obtained(p, t, K):
    i = 0
    for ch in p:
        i = t.find(ch, i) + 1
        if i == 0:
            return False
        while i in K:
            i = t.find(ch, i) + 1
            if i == 0:
                return False
    return True

I = input

t, p, A = I(), I(), list(map(int, I().split()))
L, R = 0, len(A) - 1

while L < R:
    x = (L + R + 1) // 2
    if is_obtained(p, t, set(A[:x])):
        L = x
    else:
        R = x - 1

print(L)

s1 = input()
s2 = input()
rs = list(map(int, input().split()))

def is_in(big, little):
    i, j = 0, 0
    matched = 0
    while i < len(big) and j < len(little):
        if big[i] == little[j]:
            matched += 1
            i +=1
            j += 1
        else:
            i += 1
    if matched < len(little):
        return False
    return True

def gen_st(mid):
    nonlocal s1, s2, rs
    cs = set(rs[:mid])
    n = []
    for i in range(len(s1)):
        if i+1 in cs:
            continue
        n.append(s1[i])
    #print(''.join(n), s2)
    return is_in(''.join(n), s2)

start = 0
end = len(rs)
weird = False
#print(gen_st(4))
while start < end:
    #print(start, end)
    mid = (start+end)//2
    if gen_st(mid):
        start = mid
        if start == end-1:
            weird = True
            if gen_st(end):
                print(end)
                break
            else:
                print(start)
                break
    else:
        end = mid - 1
    if not weird and start == end:
        print(start)



def check(x):
    temp=[]
    for i in t:
        temp.append(i)
    for i in range(x):
        temp[a[i]-1]=''
    #print(''.join(temp))
    l=0;r=0;c=0
    while r<len(s) and l<len(t):
        if s[r]==temp[l]:
            r+=1;c+=1
        l+=1
    #print(c)
    return c==len(s)
t=input()
s=input()
a=list(map(int,input().split()))
lo=0;hi=len(a)
while lo<hi-1:
    mid=lo+(hi-lo)//2
    #print(lo,hi,mid)
    if check(mid):
        lo=mid
    else:
        hi=mid
    
print(lo)


s = input()
t = input()
a = list(map(int, input().split()))


def exist(m):
    vis = [0] * len(s)
    for i in range(m):
        vis[a[i] - 1] = 1
    j = 0
    for i in range(len(s)):
        if vis[i] == 0:
            if s[i] == t[j]:
                j += 1
            if j == len(t):
                return 1
    return 0


l, r = 0, len(s)
while l < r:
    mid = (l + r + 1) // 2
    if exist(mid):
        l = mid
    else:
        r = mid - 1

print(l)


a = input()
b = input()
p = list(map(int,input().split()))

n = len(p)
h = [0]*n
for i in range(n):
    p[i]-=1
    h[p[i]] = i

def check(s1,s2,g):
    m1 = len(s1)
    m2 = len(s2)
    j = 0
    i = 0
      
    while j<m1 and i<m2: 
        if s1[j] == s2[i] and h[i]>g:     
            j = j+1    
        i = i + 1
    return j==m1

l = -1
r = n-1

while l<r:
    md = (l+r+1)//2
    # print(md,p[md],h[p[md]])
    if check(b,a,h[p[md]]):
        # print(md,p[md],h[p[md]])
        l = md
    else:
        r = md-1

print(l+1)

s = list(input())
t = list(input())
arr = list(x-1 for x in map(int, input().split()))
n, m = len(arr), len(t)

def binary_search():
    f, e = 0, n
    while f <= e:
        mid = f + e >> 1
        vis = [0] * n
        for i in range(mid):
            vis[arr[i]] = 1
        idx, found = 0, 0
        for i in range(n):
            if not vis[i] and s[i] == t[idx]:
                idx += 1
            if idx == m:
                found = 1
                break
        if found:
            f = mid + 1
        else:
            e = mid - 1
    return f - 1

print(binary_search())