| Codeforces Global Round 5 |
|---|
| Закончено |
Рассмотрим тоннель на односторонней дороге. В течение некоторого дня $$$n$$$ машин, пронумерованных от $$$1$$$ до $$$n$$$, въехали в тоннель и выехали из него ровно по одному разу. Все машины ехали через тоннель с постоянными скоростями.
На въезде в тоннель установлена камера безопасности дорожного движения. Ещё одна такая же камера установлена на выезде из тоннеля. Идеальный баланс.
Благодаря камерам известно, в каком порядке машины въезжали в тоннель и выезжали из него. Никакие две машины не въезжали и не выезжали одновременно.
Правила дорожного движения запрещают обгоны внутри тоннеля. Если машина $$$i$$$ обгоняет машину $$$j$$$ внутри тоннеля, машина $$$i$$$ должна быть оштрафована. Тем не менее, каждая машина может быть оштрафована не более одного раза.
Если говорить формально, то пусть машина $$$i$$$ точно обогнала машину $$$j$$$, если машина $$$i$$$ въехала в тоннель позже машины $$$j$$$, а выехала из тоннеля раньше машины $$$j$$$. Тогда машина $$$i$$$ должна быть оштрафована тогда и только тогда, когда она точно обогнала хотя бы одну другую машину.
Определите, сколько машин следует оштрафовать.
Первая строка содержит целое число $$$n$$$ ($$$2 \le n \le 10^5$$$) — число машин.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — номера машин в порядке въезда в тоннель. Все $$$a_i$$$ попарно различны.
Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$) — номера машин в порядке выезда из тоннеля. Все $$$b_i$$$ попарно различны.
Выведите число машин, которые должны быть оштрафованы.
5 3 5 2 1 4 4 3 2 5 1
2
7 5 2 3 6 7 1 4 2 3 6 7 1 4 5
6
2 1 2 1 2
0
Первый пример изображён ниже:
Машина $$$2$$$ точно обогнала машину $$$5$$$, а машина $$$4$$$ точно обогнала машины $$$1$$$, $$$2$$$, $$$3$$$ и $$$5$$$. Машины $$$2$$$ и $$$4$$$ должны быть оштрафованы.
Во втором примере машину $$$5$$$ точно обогнали все другие машины.
В третьем примере никого штрафовать не нужно.
