D. Московские гориллы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Зимой обитателям Московского зоопарка очень скучно, в частности, это касается горилл. Вы решили развлечь их и принесли в зоопарк перестановку $$$p$$$ длины $$$n$$$.

Перестановкой длины $$$n$$$ называется массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ является перестановкой, но $$$[1,2,2]$$$ не является перестановкой ($$$2$$$ встречается дважды в массиве) и $$$[1,3,4]$$$ тоже не является перестановкой ($$$n=3$$$, но $$$4$$$ присутствует в массиве).

У горилл оказалась своя перестановка $$$q$$$ длины $$$n$$$. Они предложили вам посчитать количество пар целых чисел $$$l, r$$$ ($$$1 \le l \le r \le n$$$) таких, что $$$\operatorname{MEX}([p_l, p_{l+1}, \ldots, p_r])=\operatorname{MEX}([q_l, q_{l+1}, \ldots, q_r])$$$.

$$$\operatorname{MEX}$$$ последовательности это минимальное целое положительное число, отсутствующее в этой последовательности. Например, $$$\operatorname{MEX}([1, 3]) = 2$$$, $$$\operatorname{MEX}([5]) = 1$$$, $$$\operatorname{MEX}([3, 1, 2, 6]) = 4$$$.

Вы не хотите рисковать своим здоровьем, поэтому не посмеете отказать гориллам.

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длина перестановок.

Вторая строка содержит $$$n$$$ различных целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — элементы перестановки $$$p$$$.

Третья строка содержит $$$n$$$ различных целых чисел $$$q_1, q_2, \ldots, q_n$$$ ($$$1 \le q_i \le n$$$) — элементы перестановки $$$q$$$.

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

Выведите одно целое число — количество подходящих пар $$$l$$$ и $$$r$$$.

Примеры
Входные данные
3
1 3 2
2 1 3
Выходные данные
2
Входные данные
7
7 3 6 2 1 5 4
6 7 2 5 3 1 4
Выходные данные
16
Входные данные
6
1 2 3 4 5 6
6 5 4 3 2 1
Выходные данные
11
Примечание

В первом примере подходят два отрезка — $$$[1, 3]$$$, для которого $$$\operatorname{MEX}$$$ в обоих массивах равен $$$4$$$, и $$$[3, 3]$$$, для которого $$$\operatorname{MEX}$$$ в обоих массивах равен $$$1$$$.

Во втором примере, например, подходит отрезок $$$[1, 4]$$$, а отрезок $$$[6, 7]$$$ не подходит, потому что $$$\operatorname{MEX}(5, 4) \neq \operatorname{MEX}(1, 4)$$$.