시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB0000.000%

문제

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

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

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

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

Считается, что:

  • Все вагоны одинаковой длины.
  • Каждому типу товара соответствует определенное слово --- его название ("Oil", "Wood" и т. д.)
  • Количество разгружаемых вагонов первого состава с товарами любого типа совпадает с количеством загружаемых вагонов второго состава для товаров такого же типа.
  • Может быть несколько вагонов первого состава с одинаковым типом товара. При этом любой из них можно перегружать в соответствующие вагоны второго состава (но только полностью).
  • Если вагон первого состава с определенным типом товара встал рядом с вагоном второго состава, предназначенного для данного типа груза, то Пекка может как осуществить перегрузку, так и отказаться от нее.
  • Изначально составы стоят таким образом, что первый вагон первого состава стоит рядом с первым вагоном второго состава, а последний вагон первого состава --- рядом с последним вагоном второго состава.

입력

В первой строке входного файла записано количество вагонов в составах $N$ ($1\le N\le100\,000$). Далее следуют $N$ строк, описывающих вагоны первого состава в порядке, в котором они соединены в состав. В каждой строке записано название груза, находящегося в соответствующем вагоне. Название содержит от одной до десяти больших и маленьких букв латинского алфавита. Названия считаются одинаковыми, если они совпадают с учетом регистра (например, "Oil" и "oil" --- разные грузы). Затем записаны $N$ строк, аналогичным образом описывающих вагоны второго состава.

출력

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

예제 입력 1

3
Oil
Wood
Grain
Wood
Grain
Oil

예제 출력 1

4