Triangular Paths
Consider an infinite triangle made up of layers. Let's number the layers, starting from one, from the top of the triangle (from top to bottom). The $$$k$$$-th layer of the triangle contains $$$k$$$ points, numbered from left to right. Each point of an infinite triangle is described by a pair of numbers $$$(r, c)$$$ ($$$1 \le c \le r$$$), where $$$r$$$ is the number of the layer, and $$$c$$$ is the number of the point in the layer. From each point $$$(r, c)$$$ there are two directed edges to the points $$$(r+1, c)$$$ and $$$(r+1, c+1)$$$, but only one of the edges is activated. If $$$r + c$$$ is even, then the edge to the point $$$(r+1, c)$$$ is activated, otherwise the edge to the point $$$(r+1, c+1)$$$ is activated. Look at the picture for a better understanding.  Activated edges are colored in black. Non-activated edges are colored in gray. From the point $$$(r_1, c_1)$$$ it is possible to reach the point $$$(r_2, c_2)$$$, if there is a path between them only from activated edges. For example, in the picture above, there is a path from $$$(1, 1)$$$ to $$$(3, 2)$$$, but there is no path from $$$(2, 1)$$$ to $$$(1, 1)$$$.Initially, you are at the point $$$(1, 1)$$$. For each turn, you can:   Replace activated edge for point $$$(r, c)$$$. That is if the edge to the point $$$(r+1, c)$$$ is activated, then instead of it, the edge to the point $$$(r+1, c+1)$$$ becomes activated, otherwise if the edge to the point $$$(r+1, c+1)$$$, then instead if it, the edge to the point $$$(r+1, c)$$$ becomes activated. This action increases the cost of the path by $$$1$$$;  Move from the current point to another by following the activated edge. This action does not increase the cost of the path. You are given a sequence of $$$n$$$ points of an infinite triangle $$$(r_1, c_1), (r_2, c_2), \ldots, (r_n, c_n)$$$. Find the minimum cost path from $$$(1, 1)$$$, passing through all $$$n$$$ points in arbitrary order.
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) is the number of test cases. Then $$$t$$$ test cases follow.Each test case begins with a line containing one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) is the number of points to visit.The second line contains $$$n$$$ numbers $$$r_1, r_2, \ldots, r_n$$$ ($$$1 \le r_i \le 10^9$$$), where $$$r_i$$$ is the number of the layer in which $$$i$$$-th point is located.The third line contains $$$n$$$ numbers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le r_i$$$), where $$$c_i$$$ is the number of the $$$i$$$-th point in the $$$r_i$$$ layer.It is guaranteed that all $$$n$$$ points are distinct.It is guaranteed that there is always at least one way to traverse all $$$n$$$ points.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output the minimum cost of a path passing through all points in the corresponding test case.
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
MOD = 10 ** 9 + 7

def solve():
    n = int(input())
    R = list(map(int, input().split()))
    C = list(map(int, input().split()))
    points = [(r, c) for (r, c) in zip(R, C)]
    points.sort()
    res = 0
    pr = pc = 1
    for (r, c) in points:
        if r - c == pr - pc:
            if (r + c) % 2 == 0:
                res += r - pr
        else:
            if pc != c:
                pr += c - pc
                pc = c
            if (pr + pc) % 2 == 0:
                res += (r - pr) // 2
            else:
                res += (r - pr + 1) // 2
        (pr, pc) = (r, c)
    print(res)
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        solve()
def solve():
    n = int(input())
    points = []
    x = input()
    x = [int(i) for i in x.split(' ')]
    for i in x:
        points.append([i, 0])
    y = input()
    y = [int(i) for i in y.split(' ')]
    for (i, v) in enumerate(y):
        points[i][1] = v
    points.sort()
    ans = 0
    start = [1, 1]
    for (x, y) in points:
        (a, b) = start
        if x - y == a - b:
            if (a - b) % 2 == 0:
                ans += y - b
        else:
            ans += (x - y) // 2 - (a - b) // 2
        start = [x, y]
    print(ans)

def main():
    t = int(input())
    while t:
        solve()
        t -= 1
if __name__ == '__main__':
    main()
import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.buffer.readline())

def LI():
    return list(map(int, sys.stdin.buffer.readline().split()))

def LI1():
    return list(map(int1, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def LLI1(rows_number):
    return [LI1() for _ in range(rows_number)]

def BI():
    return sys.stdin.buffer.readline().rstrip()

def SI():
    return sys.stdin.buffer.readline().rstrip().decode()
dij = [(0, 1), (-1, 0), (0, -1), (1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
inf = 10 ** 16
md = 10 ** 9 + 7
for _ in range(II()):
    n = II()
    rr = LI()
    cc = LI()
    rc = [(r, c) for (r, c) in zip(rr, cc)]
    rc.sort()
    ans = 0
    now = 0
    pr = 1
    for (r, c) in rc:
        nxt = r - c
        if now < nxt:
            if now & 1:
                ans += (nxt - now + 1) // 2
            else:
                ans += (nxt - now) // 2
        elif now > nxt:
            if now & 1:
                ans += (nxt - now) // 2
            else:
                ans += (nxt - now + 1) // 2
        elif now & 1 == 0:
            ans += r - pr
        now = nxt
        pr = r
    print(ans)