Зимой обитателям Московского зоопарка очень скучно, в частности, это касается горилл. Вы решили развлечь их и принесли в зоопарк перестановку \(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\).
Вы не хотите рисковать своим здоровьем, поэтому не посмеете отказать гориллам.
Примечание
В первом примере подходят два отрезка — \([1, 3]\), для которого \(\operatorname{MEX}\) в обоих массивах равен \(4\), и \([3, 3]\), для которого \(\operatorname{MEX}\) в обоих массивах равен \(1\).
Во втором примере, например, подходит отрезок \([1, 4]\), а отрезок \([6, 7]\) не подходит, потому что \(\operatorname{MEX}(5, 4) \neq \operatorname{MEX}(1, 4)\).