| Codeforces Round 402 (Div. 1) |
|---|
| Закончено |
Любимое занятие Насти — вычеркивать буквы из слова, чтобы получилось другое слово. Но получается это у нее довольно плохо, потому что она еще маленькая. Поэтому ей всегда помогает ее старший брат Сергей.
Сергей дал Насте слово t и хочет, чтобы из него получилось слово p. Настя начинает вычеркивать буквы в некотором порядке (последовательно, строго в этом порядке), который задан перестановкой номеров букв слова t: a1... a|t|. Длину слова x мы обозначаем |x|. Заметим, что после вычеркивания буквы нумерация не меняется. Например, если t = «nastya» и a = [4, 1, 5, 3, 2, 6] тогда вычеркивания образуют следующую последовательность слов: «nastya» 
«nastya» «nastya» «nastya» «nastya» «nastya» «nastya».
Этот порядок изначально известен Сергею. Его задача состоит в том, чтобы в некоторый момент времени остановить сестру и закончить вычеркивание самому, получив после этого слово p. Так как Насте нравится это занятие, Сергей хочет остановить ее как можно позже. Ваша задача — сообщить, сколько букв может вычеркнуть Настя до того, как ее остановит Сергей.
Гарантируется, что слово p можно получить вычеркиванием букв из t.
Первая и вторая строки входного файла содержат слова t и p, соответственно. Слова состоят из строчных букв латинского алфавита (1 ≤ |p| < |t| ≤ 200 000). Гарантируется, что слово p можно получить вычеркиванием букв из t.
Следующая строка содержит перестановку a1, a2, ..., a|t| номеров букв, задающую порядок, в котором Настя вычеркивает буквы слова t (1 ≤ ai ≤ |t|, все ai различны).
Выведите одно число — максимальное число букв, которые может вычеркнуть Настя.
ababcba
abb
5 3 4 1 7 6 2
3
bbbabb
bb
1 6 3 4 2 5
4
В первом примере последовательность вычеркивания букв Настей выглядит так:
«ababcba» «ababcba» «ababcba» «ababcba»
Продолжать вычеркивать Настя не может, потому что из «ababcba» нельзя получить «abb».
Таким образом, Настя может вычеркнуть только три буквы в свой последовательности.
