C. Monopatitime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a grid $$$a$$$ of $$$2$$$ rows and $$$n$$$ columns, where every cell has value from $$$1$$$ to $$$2n$$$.Let $$$f(l, r)$$$, where $$$1 \le l \le r \le 2n$$$, represent a binary$$$^{\text{∗}}$$$ grid $$$b$$$ of $$$2$$$ rows and $$$n$$$ columns, such that $$$b_{i, j} = 1$$$ if and only if $$$l \le a_{i, j} \le r$$$. Note that cell $$$(i, j)$$$ denotes the cell $$$i$$$ rows from the top and $$$j$$$ columns from the left.Count the number of pairs of integers $$$(l, r)$$$ such that $$$1 \le l \le r \le 2n$$$, and in $$$f(l, r)$$$ there exists a down-right path of adjacent cells$$$^{\text{†}}$$$ with value of $$$1$$$ from cell $$$(1, 1)$$$ to $$$(2, n)$$$.$$$^{\text{∗}}$$$A grid is considered binary if and only if every cell of it has value of $$$\mathtt{0}$$$ or $$$\mathtt{1}$$$.$$$^{\text{†}}$$$A down-right path of adjacent cells is a sequence of cells such that each cell in the sequence shares either its top side or its left side with a side of the previous cell in the sequence.InputEach test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows. The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of columns in the grid.The second line contains exactly $$$n$$$ integers $$$a_{1, 1}$$$, $$$a_{1, 2}$$$, ..., $$$a_{1, n}$$$ ($$$1 \le a_{1, i} \le 2n$$$) — the values of the cells of the first row of the grid.The third line contains exactly $$$n$$$ integers $$$a_{2, 1}$$$, $$$a_{2, 2}$$$, ..., $$$a_{2, n}$$$ ($$$1 \le a_{2, i} \le 2n$$$) — the values of the cells of the second row of the grid.It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.OutputFor every test case, output on a separate line a single integer representing the number of pairs of integers $$$(l, r)$$$ such that $$$1 \le l \le r \le 2n$$$, and in $$$f(l, r)$$$ there exists a down-right path of adjacent cells with value of $$$1$$$ from cell $$$(1, 1)$$$ to $$$(2, n)$$$.ExampleInput521 33 131 2 33 2 141 5 5 55 3 1 248 8 8 88 8 8 866 6 5 7 9 121 4 2 8 5 6Output254825NoteConsider the first example.The grids $$$f(1, 1), f(1, 2)$$$ will look like the following:$$$$$$ \mathtt{10} $$$$$$ $$$$$$ \mathtt{01} $$$$$$There does not exist a path of $$$1$$$s from the top-left cell to the bottom-right cell, therefore the pairs $$$(1, 1)$$$ and $$$(1, 2)$$$ are not counted.The grids $$$f(1, 3)$$$ and $$$f(1, 4)$$$ will look like the following:$$$$$$ \mathtt{11} $$$$$$ $$$$$$ \mathtt{11} $$$$$$Since there exists a valid path from $$$(1, 1)$$$ to $$$(2, 2)$$$, the pairs $$$(1, 3)$$$ and $$$(1, 4)$$$ will be counted.The grids $$$f(2, 2)$$$, $$$f(4, 4)$$$ will be the following:$$$$$$ \mathtt{00} $$$$$$ $$$$$$ \mathtt{00} $$$$$$The grids $$$f(2, 3)$$$, $$$f(2, 4)$$$, $$$f(3, 3)$$$, $$$f(3, 4)$$$ will look like the following:$$$$$$ \mathtt{01} $$$$$$ $$$$$$ \mathtt{10} $$$$$$So the pairs $$$(2, 3)$$$, $$$(2, 4)$$$, $$$(3, 3)$$$ and $$$(3, 4)$$$ will not be counted.The only pairs counted where pairs $$$(1, 3)$$$ and $$$(1, 4)$$$, so the answer is $$$2$$$.