给定两个大小为 $$$m$$$ 的数组 $$$x$$$ 和 $$$y$$$,让 $$$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$$$ 上 $$$z_i=y_i$$$ 的最大位置数。
给定两个整数序列 $$$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$$$。
输出
对于每个测试用例,输出所有 $$$(l,r)$$$ 对的 $$$f([a_l,a_{l+1},\ldots,a_r], [b_l,b_{l+1},\ldots,b_r])$$$ 之和。
示例
输入复制
635 3 14 2 151 2 3 4 51 2 3 4 567 1 12 10 5 89 2 4 3 6 511265 1 2 6 3 43 1 6 5 2 422 21 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]$$$。