CF2163C Monopati

You 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.

Each 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 $ .

For 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) $ .

Consider 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 $ .