CF2137F Prefix Maximum Invariance

给定两个长度均为 $m$ 的数组 $x$ 和 $y$，设 $z$ 是另一个长度为 $m$ 的数组，且 $z$ 每个位置的**前缀最大值**与 $x$ 对应位置的前缀最大值相同。形式化地说，需满足对所有 $1 \leq i \leq m$，都有 $\max(x_1,x_2,\ldots,x_i) = \max(z_1,z_2,\ldots,z_i)$。 定义 $f(x,y)$ 为：在所有满足上述条件的数组 $z$ 中，$z_i = y_i$ 的位置的**最大数量**。 现给定两个长度均为 $n$ 的整数序列 $a$ 和 $b$，请计算双重求和 $\sum_{l=1}^n \sum_{r=l}^n f\left( a[l..r], b[l..r] \right)$ 的结果。其中 $a[l..r]$ 表示数组 $a$ 中从第 $l$ 个元素到第 $r$ 个元素的子数组（即 $[a_l,a_{l+1},\ldots,a_r]$），$b[l..r]$ 表示数组 $b$ 中从第 $l$ 个元素到第 $r$ 个元素的子数组（即 $[b_l,b_{l+1},\ldots,b_r]$）。

每组测试包含多组测试用例。第一行输入测试用例的数量 $t$（$1 \leq t \leq 10^4$），随后依次描述每组测试用例。 每组测试用例的输入格式如下： - 第一行：一个整数 $n$（$1 \leq n \leq 2 \times 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 \times 10^5$。

对于每组测试用例，输出一个整数——即上述双重求和的结果。 _（注：英文原题面中“the final value of $f(a)$ assuming both players play optimally”为笔误，结合题目描述与样例，实际需输出上述双重求和结果）_

在第一个测试用例中，答案是以下各项的和： - $f(a[1..1], b[1..1]) = f([5],[4]) = 0$，此时使用的 $z$ 数组为 $[5]$； - $f(a[2..2], b[2..2]) = f([3],[2]) = 0$，此时使用的 $z$ 数组为 $[3]$； - $f(a[3..3], b[3..3]) = f([1],[1]) = 1$，此时使用的 $z$ 数组为 $[1]$； - $f(a[1..2], b[1..2]) = f([5,3],[4,2]) = 1$，此时使用的 $z$ 数组为 $[5,2]$； - $f(a[2..3], b[2..3]) = f([3,1],[2,1]) = 1$，此时使用的 $z$ 数组为 $[3,1]$； - $f(a[1..3], b[1..3]) = f([5,3,1],[4,2,1]) = 2$，此时使用的 $z$ 数组为 $[5,2,1]$。