Задача №114937. Московские гориллы
Зимой обитателям Московского зоопарка очень скучно, в частности, это касается горилл. Вы решили развлечь их и принесли в зоопарк перестановку \(p\) длины \(n\).
Напомним, что перестановкой длины \(n\) называется последовательность целых чисел от \(1\) до \(n\), в которой каждое такое число встречается ровно один раз. Например, последовательности \([3, 1, 2]\) и \([1, 4, 2, 3]\) являются перестановками, а последовательности \([3, 4]\) и \([1, 2, 2, 3]\) нет.
У горилл помимо вашей оказалась и своя перестановка \(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\).
Выведите одно целое число — ответ на задачу.
Обратите внимание, что ответ может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать и с типом int.
В данной задаче \(53\) теста, помимо тестов из условия. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.
Тесты разбиты на четыре группы. Проверка на тестах второй группы проводится только при прохождении всех тестов первой группы. Проверка на тестах четвертой группы проводится только при прохождении всех тестов всех предыдущих групп. При этом баллы начисляются за каждый пройденный тест.
Тесты первой группы удовлетворяют условию \(n \leq 400\). Решения, корректно работающие на тестах этой группы, наберут не менее \(20\) баллов.
Тесты второй группы удовлетворяют условию \(n \leq 5000\). Решения, корректно работающие на тестах этой группы, наберут не менее \(42\) баллов.
Тесты третьей группы удовлетворяют условию \(p_i = i\), \(q_i = n - i + 1\). Решения, корректно работающие на тестах этой группы, наберут не менее \(16\) баллов.
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