F. Префиксная максимальная инвариантность
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны два массива $$$x$$$ и $$$y$$$ размером $$$m$$$, пусть $$$z$$$ будет другим массивом размером $$$m$$$, такой что префиксный максимум в каждой позиции $$$z$$$ совпадает с префиксным максимумом в каждой позиции $$$x$$$. Формально, должно выполняться равенство $$$\operatorname{max}(x_1,x_2,\ldots,x_i)=\operatorname{max}(z_1,z_2,\ldots,z_i)$$$ для всех $$$1 \leq i \leq m$$$. Определим $$$f(x,y)$$$ как максимальное количество позиций, где $$$z_i=y_i$$$, для всех возможных массивов $$$z$$$.

Вам даны две последовательности целых чисел $$$a$$$ и $$$b$$$, обе размером $$$n$$$. Пожалуйста, найдите значение $$$\sum_{l=1}^n\sum_{r=l}^n f([a_l,a_{l+1},\ldots,a_r], [b_l,b_{l+1},\ldots,b_r])$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

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

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ $$$(1 \leq a_i \leq 2\cdot n)$$$.

Третья строка каждого набора содержит $$$n$$$ целых чисел $$$b_1,b_2,\ldots,b_n$$$ $$$(1 \leq b_i \leq 2\cdot n)$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.

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

Для каждого набора входных данных выведите сумму $$$f([a_l,a_{l+1},\ldots,a_r], [b_l,b_{l+1},\ldots,b_r])$$$ для всех пар $$$(l,r)$$$.

Пример
Входные данные
6
3
5 3 1
4 2 1
5
1 2 3 4 5
1 2 3 4 5
6
7 1 12 10 5 8
9 2 4 3 6 5
1
1
2
6
5 1 2 6 3 4
3 1 6 5 2 4
2
2 2
1 1
Выходные данные
5
35
26
0
24
1
Примечание

В первом примере ответ является суммой следующих значений:

  • $$$f([5],[4])=0$$$, используя $$$z=[5]$$$.
  • $$$f([3],[2])=0$$$, используя $$$z=[3]$$$.
  • $$$f([1],[1])=1$$$, используя $$$z=[1]$$$.
  • $$$f([5,3],[4,2])=1$$$, используя $$$z=[5,2]$$$.
  • $$$f([3,1], [2,1])=1$$$, используя $$$z=[3,1]$$$.
  • $$$f([5,3,1],[4,2,1])=2$$$, используя $$$z=[5,2,1]$$$.