← К соревнованиям

Sort Me Round

Закрытие Макдоналдса

Сложность: 54%

Сегодня последний день работы Макдоналдса, поэтому в него пришли целых mm покупателей и выстроились в очередь. У каждого из них есть желанный товар pip_i. На вкус и цвет товарищей нет, поэтому предпочтения у каждого покупателя отличаются.

Макдоналдс просто не успеет выслушать заказ каждого покупателя и приготовить его. Поэтому руководство решило наготовить кучу еды заранее и поставить её на конвейерную ленту, которая поочерёдно будет отдавать кассиру товар – в любой момент времени можно взять только первый товар, после чего все остальные товары проедут по ленте вперёд, и бывший второй товар станет первым. Макдоналдс положил на ленту nn товаров, каждый из которых имеет свой вид aia_i, и запустил людей в ресторан.

Когда подходит очередной человек, кассир может сколько угодно раз отдать ему набор с конвейнера. Покупатель останется довольным только в том случае, если среди полученных товаров найдётся его желанный товар.

Понятно, что угодить всем покупателям не получится, но, чтобы было хоть немного больше шансов, Макдоналдс нанял гипнотизера. Он может загипнотизировать всех покупателей, и в это время переместить ровно одного человека в любое место (может даже оставить его на своем месте).

Руководство Макдоналдса хочет узнать максимально возможное количество людей, которые могут остаться довольными после обслуживания всей очереди.

Входные данные

В первой строке записаны два числа nn и mm – количество товаров на ленте и количество людей в очереди. (1n,m21051 \le n, m \le 2 \cdot 10^5)

Во второй строке записано nn чисел a1,a2,ana_1, a_2, \dots a_n – товары на ленте. (1aim1 \le a_i \le m)

В трейтьей строке записано mm чисел p1,p2,pmp_1, p_2, \dots p_m – желанные товары у покупателей в очереди. (1pim1 \le p_i \le m)

Выходные данные

Выведите одно число – максимально возможное количество людей, которые могут остаться довольными после обслуживания всей очереди.

Подзадачи

баллынеобх. подзадачиограничения
1

10

-

n,m50n, m \le 50

2

10

1

n,m150n, m \le 150

3

25

2

n,m5000n, m \le 5000

4

55

3

n,m2105n, m \le 2 \cdot 10^5

STDINSTDOUT
4 3
3 2 3 1
3 1 2
3