Monocarp is playing a computer game once again. He is a wizard apprentice, who only knows a single spell. Luckily, this spell can damage the monsters.

The level he's currently on contains $n$ monsters. The $i$-th of them appears $k_i$ seconds after the start of the level and has $h_i$ health points. As an additional constraint, $h_i \le k_i$ for all $1 \le i \le n$. All $k_i$ are different.

Monocarp can cast the spell at moments which are positive integer amounts of second after the start of the level: $1, 2, 3, \dots$ The damage of the spell is calculated as follows. If he didn't cast the spell at the previous second, the damage is $1$. Otherwise, let the damage at the previous second be $x$. Then he can choose the damage to be either $x + 1$ or $1$. A spell uses mana: casting a spell with damage $x$ uses $x$ mana. Mana doesn't regenerate.

To kill the $i$-th monster, Monocarp has to cast a spell with damage at least $h_i$ at the exact moment the monster appears, which is $k_i$.

Note that Monocarp can cast the spell even when there is no monster at the current second.

The mana amount required to cast the spells is the sum of mana usages for all cast spells. Calculate the least amount of mana required for Monocarp to kill all monsters.

It can be shown that it's always possible to kill all monsters under the constraints of the problem.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of the testcase contains a single integer $n$ ($1 \le n \le 100$) — the number of monsters in the level.

The second line of the testcase contains $n$ integers $k_1 < k_2 < \dots < k_n$ ($1 \le k_i \le 10^9$) — the number of second from the start the $i$-th monster appears at. All $k_i$ are different, $k_i$ are provided in the increasing order.

The third line of the testcase contains $n$ integers $h_1, h_2, \dots, h_n$ ($1 \le h_i \le k_i \le 10^9$) — the health of the $i$-th monster.

The sum of $n$ over all testcases doesn't exceed $10^4$.


-----Output-----

For each testcase, print a single integer — the least amount of mana required for Monocarp to kill all monsters.


-----Examples-----

Input
3
1
6
4
2
4 5
2 2
3
5 7 9
2 1 2
Output
10
6
7


-----Note-----

In the first testcase of the example, Monocarp can cast spells $3, 4, 5$ and $6$ seconds from the start with damages $1, 2, 3$ and $4$, respectively. The damage dealt at $6$ seconds is $4$, which is indeed greater than or equal to the health of the monster that appears.

In the second testcase of the example, Monocarp can cast spells $3, 4$ and $5$ seconds from the start with damages $1, 2$ and $3$, respectively.

In the third testcase of the example, Monocarp can cast spells $4, 5, 7, 8$ and $9$ seconds from the start with damages $1, 2, 1, 1$ and $2$, respectively.

Difficulty: MEDIUM_HARD
Tags: Sorting

Amortized analysis

Implementation

Greedy algorithms

Dynamic programming

Mathematics

Data structures
Skill types: Sorting

Amortized analysis

Greedy algorithms

Dynamic programming

Data structures

Starter code:

Solutions:
import sys
inp = sys.stdin.readline

def getCost(a: int):
	return a * (a + 1) // 2
for _ in range(int(inp())):
	n = int(inp())
	k = list(map(int, inp().split()))
	h = list(map(int, inp().split()))
	ans = 0
	segEnd = len(k) - 1
	segMax = len(k) - 1
	for i in range(len(k) - 2, -1, -1):
		if h[segMax] <= k[segMax] - k[i]:
			ans += getCost(h[segMax] + (k[segEnd] - k[segMax]))
			segEnd = i
			segMax = i
		elif h[i] + k[segMax] - k[i] > h[segMax]:
			segMax = i
	ans += getCost(h[segMax] + (k[segEnd] - k[segMax]))
	print(ans)


import sys

def solve():
	inp = sys.stdin.readline
	inp()
	k = list(map(int, inp().split()))
	h = list(map(int, inp().split()))
	i = 0
	while i < len(h):
		j = i + 1
		while j < len(h):
			s = k[j] - h[j] + 1
			if s <= k[i]:
				if h[j] < h[i] + (k[j] - k[i]):
					h[j] = h[i] + (k[j] - k[i])
				h.pop(i)
				k.pop(i)
				i -= 1
				break
			else:
				j += 1
		i += 1
	ans = 0
	for i in h:
		ans += i * (i + 1) // 2
	print(ans)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import sys
input = sys.stdin.readline

def helper(a):
	return a * (a + 1) // 2

def solve(n, arr):
	ans = helper(arr[0][1])
	curr = arr[0][1]
	for i in range(1, n):
		d = arr[i][0] - arr[i - 1][0]
		if d >= arr[i][1]:
			ans += helper(arr[i][1])
			curr = arr[i][1]
		else:
			ans += helper(curr + d) - helper(curr)
			curr += d
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	k = list(map(int, input().split()))
	h = list(map(int, input().split()))
	arr = list(zip(k, h))
	arr.sort(key=lambda x: x[0] - x[1])
	a = []
	a.append(arr[0])
	for i in range(1, n):
		if arr[i][0] > a[-1][0]:
			a.append(arr[i])
	print(solve(len(a), a))


import sys
input = sys.stdin.readline
ans = []
for _ in range(int(input())):
	n = int(input())
	k = list(map(int, input().split()))
	h = list(map(int, input().split()))
	a = 0
	p = h[-1]
	q = k[-1]
	for i in range(n - 2, -1, -1):
		d = p - (q - k[i])
		if d > 0:
			if d < h[i]:
				p += h[i] - d
		else:
			a += (1 + p) * p // 2
			p = h[i]
			q = k[i]
	a += (1 + p) * p // 2
	ans.append(a)
for i in ans:
	print(i)


answer = []
for _ in range(int(input())):
	n = int(input())
	k = list(map(int, input().split()))
	h = list(map(int, input().split()))
	count = 0
	k_r = k[-1]
	k_l = k[-1] - h[-1] + 1
	for i in range(n - 2, -1, -1):
		if k_l <= k[i]:
			pass
		else:
			count += (k_r - k_l + 2) * (k_r - k_l + 1) // 2
			k_r = k[i]
		k_l = min(k_l, k[i] - h[i] + 1)
	count += (k_r - k_l + 2) * (k_r - k_l + 1) // 2
	answer.append(count)
print('\n'.join(map(str, answer)))


t = int(input())
ans = []
while t > 0:
	t -= 1
	n = int(input())
	otv = 0
	time = list(map(int, input().split()))
	x = list(map(int, input().split()))
	st = []
	for i in range(n):
		st.append([time[i] - x[i], time[i]])
	st.sort()
	(l, r) = (-1, -1)
	for it in st:
		if it[0] >= r:
			otv += (r - l) * (r - l + 1) // 2
			(l, r) = it
		else:
			r = max(r, it[1])
	otv += (r - l) * (r - l + 1) // 2
	ans.append(otv)
print('\n'.join([str(i) for i in ans]))


from array import array
results = []
for _ in range(int(input())):
	n = int(input())
	time = array('Q', map(int, input().split()))
	hp = array('Q', map(int, input().split()))
	interval = None
	mana = 0
	for index in range(n - 1, -1, -1):
		if interval is None:
			interval = (time[index] - hp[index] + 1, time[index])
		elif interval[0] <= time[index]:
			begin = min(interval[0], time[index] - hp[index] + 1)
			interval = (begin, interval[1])
		else:
			length = interval[1] - interval[0] + 1
			mana += length * (length + 1) // 2
			interval = (time[index] - hp[index] + 1, time[index])
	length = interval[1] - interval[0] + 1
	mana += length * (length + 1) // 2
	results.append(str(mana))
print('\n'.join(results))


import math
import random
from collections import Counter, deque
from sys import stdout
import time
from math import factorial, log, gcd
import sys
from decimal import Decimal
import heapq
from copy import deepcopy

def S():
	return sys.stdin.readline().split()

def I():
	return [int(i) for i in sys.stdin.readline().split()]

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

def IS():
	return sys.stdin.readline().replace('\n', '')

def main():
	n = II()
	t = I()
	h = I()
	ans = (1 + h[-1]) * h[-1] // 2
	dp = [(0, 0) for _ in range(n)]
	dp[-1] = (t[-1] - h[-1] + 1, h[-1])
	for i in range(n - 2, -1, -1):
		(health, _time) = (h[i], t[i])
		(pre_start, pre_col) = dp[i + 1]
		start = _time - health + 1
		if pre_start <= _time and _time - pre_start + 1 >= health:
			dp[i] = dp[i + 1]
		elif pre_start <= _time:
			ans -= pre_col * (pre_col + 1) // 2
			d = pre_col - (_time - pre_start + 1) + health
			ans += d * (d + 1) // 2
			dp[i] = (start, d)
		else:
			ans += (health + 1) * health // 2
			dp[i] = (start, health)
	print(ans)
for _ in range(II()):
	main()


t = int(input())
out = ''
for _ in range(t):
	n = int(input())
	k = [int(x) for x in input().split()]
	h = [int(x) for x in input().split()]
	last = k[-1]
	value = h[-1]
	for i in range(n - 2, -1, -1):
		h[i] = max(h[i], value - (last - k[i]))
		last = k[i]
		value = h[i]
	last = 0
	value = 0
	total = 0
	for i in range(n):
		if last >= k[i] - (h[i] - 1):
			total += (k[i] - last) * (value + 1 + value + k[i] - last) // 2
			value += k[i] - last
		else:
			total += (h[i] + 1) * h[i] // 2
			value = h[i]
		last = k[i]
	out += str(int(total)) + '\n'
print(out)


for iq in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	k = -1
	ans = 0
	for i in range(n - 2, -1, -1):
		vz = b[k] + a[i] - a[k]
		if vz <= 0:
			ans += b[k] * (b[k] + 1) // 2
			k = i
		elif vz < b[i]:
			b[k] += b[i] - vz
	ans += b[k] * (b[k] + 1) // 2
	print(ans)


for _ in range(int(input())):
	n = int(input())
	k = list(map(int, input().split()))
	h = list(map(int, input().split()))
	st = []
	for i in range(n):
		st.append([k[i] - h[i] + 1, k[i]])
	st.sort()
	(l, r) = (-2, -1)
	ans = 0
	for it in st:
		if it[0] > r:
			if l != -2 and r != -1:
				ans += (r - l + 1) * (r - l + 2) // 2
			(l, r) = it
		else:
			r = max(r, it[1])
	if l != -2 and r != -1:
		ans += (r - l + 1) * (r - l + 2) // 2
	print(ans)


def processing(monster, power, n):
	ans = 0
	span = power[-1]
	tail = monster[-1]
	for i in reversed(range(n - 1)):
		if monster[i] <= tail - span:
			ans += span * (span + 1) // 2
			span = power[i]
			tail = monster[i]
		elif tail - span + 1 <= monster[i] - power[i]:
			continue
		else:
			span = power[i] + tail - monster[i]
	ans += span * (span + 1) // 2
	return ans
t = int(input())
while t > 0:
	n = int(input())
	monster = [int(i) for i in input().split()]
	power = [int(i) for i in input().split()]
	print(processing(monster, power, n))
	t -= 1


def solve(s, h):
	ramps = []
	i = len(h) - 1
	end_ramp = s[i]
	start_ramp = s[i] - h[i]
	i -= 1
	while 1:
		if i < 0:
			break
		if s[i] > start_ramp:
			if h[i] <= s[i] - start_ramp:
				pass
			else:
				start_ramp = s[i] - h[i]
		else:
			ramps.append([start_ramp, end_ramp])
			end_ramp = s[i]
			start_ramp = s[i] - h[i]
		i -= 1
	ramps.append([start_ramp, end_ramp])
	sum = 0
	for i in ramps:
		dur = i[1] - i[0]
		sum += dur * (dur + 1) // 2
	return sum
n = int(input())
for i in range(n):
	input()
	(*s,) = map(int, input().split())
	(*h,) = map(int, input().split())
	print(solve(s, h))


import sys
from math import *
T = int(input())
for _ in range(T):
	n = int(input())
	t = list(map(int, input().split()))
	h = list(map(int, input().split()))
	for i in range(n - 2, -1, -1):
		h[i] = max(h[i], h[i + 1] - (t[i + 1] - t[i]))
	for i in range(1, n):
		if h[i] > t[i] - t[i - 1]:
			h[i] = h[i - 1] + (t[i] - t[i - 1])
	s = 0
	i = 0
	while i < n - 1:
		if h[i + 1] <= t[i + 1] - t[i]:
			s += h[i] * (h[i] + 1) // 2
		i += 1
	s += h[-1] * (h[-1] + 1) // 2
	print(s)


import sys
from math import sqrt, gcd
from collections import deque, Counter
sys.setrecursionlimit(10 ** 8)
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 1000000007
for _ in range(I()):
	n = I()
	k = L()
	h = L()
	ans = [[h[0] * (h[0] + 1) // 2, 0]]
	d = {0: h[0]}
	for i in range(1, n):
		while ans and d[ans[-1][1]] + k[i] - k[ans[-1][1]] < h[i]:
			ans.pop()
		if not ans:
			ans.append([h[i] * (h[i] + 1) // 2, i])
			d[i] = h[i]
		elif k[i] - k[ans[-1][1]] >= h[i]:
			ans.append([h[i] * (h[i] + 1) // 2, i])
			d[i] = h[i]
		else:
			diff = k[i] - k[ans[-1][1]]
			var = d[ans[-1][1]]
			ans.append([var * diff + diff * (diff + 1) // 2, i])
			d[i] = diff + var
	fans = 0
	for i in ans:
		fans += i[0]
	print(fans)


for j in range(int(input())):
	n = int(input())
	ks = list(map(int, input().split()))
	hs = list(map(int, input().split()))
	ks.insert(0, 0)
	hs.insert(0, 0)
	ind = n
	curr = hs[ind]
	su = 0
	for i in range(n - 1, -1, -1):
		if ks[ind] - ks[i] < curr:
			curr += max(0, hs[i] - (curr - (ks[ind] - ks[i])))
		else:
			su += curr * (curr + 1) // 2
			curr = hs[i]
			ind = i
	print(su)


for i in range(int(input())):
	n = int(input())
	k = list(map(int, input().split()))
	h = list(map(int, input().split()))
	l = [h[n - 1]]
	c = 0
	r = k[n - 1] - h[n - 1] + 1
	ks = k[n - 1]
	hs = h[n - 1]
	for j in range(n - 2, -1, -1):
		if r <= k[j] - h[j] + 1:
			continue
		elif r <= k[j]:
			r = k[j] - h[j] + 1
			hs = ks - r + 1
			l[c] = hs
		else:
			c += 1
			l.append(h[j])
			r = k[j] - h[j] + 1
			ks = k[j]
			hs = h[j]
	s = 0
	for j in range(c + 1):
		s += l[j] * (l[j] + 1) // 2
	print(s)


t = int(input())
for i in range(t):
	n = int(input())
	seconds = [int(el) for el in input().split(' ')]
	points = [int(el) for el in input().split(' ')]
	current = points[-1]
	for z in range(n - 2, -1, -1):
		h = points[z]
		diff = seconds[z + 1] - seconds[z]
		points[z] = max([h, current - diff])
		current = points[z]
	total = points[0] * (points[0] + 1) // 2
	current = points[0]
	for j in range(1, n):
		diff = seconds[j] - seconds[j - 1]
		h = points[j]
		if h <= diff:
			current = h
			total += h * (h + 1) // 2
		else:
			total += current * diff + diff * (diff + 1) // 2
			current += diff
	print(total)


def tr(n):
	return n * (n + 1) // 2
tests = int(input())
for test in range(tests):
	n = int(input())
	k = list(map(int, input().split()))
	h = list(map(int, input().split()))
	res = 0
	curh = 0
	curk = 2 * 10 ** 9
	for i in range(n - 1, -1, -1):
		if curk - k[i] >= curh:
			res += tr(curh)
			curk = k[i]
			curh = h[i]
		else:
			curh = max(curh, h[i] + curk - k[i])
	res += tr(curh)
	print(res)


for _ in range(int(input())):
	n = int(input())
	k = list(map(int, input().split()))
	h = list(map(int, input().split()))
	s = []
	for i in range(n):
		s.append((k[i] - h[i] + 1, k[i]))
	ans = []
	i = n - 1
	while i != 0:
		a = s[i]
		b = s[i - 1]
		if a[0] <= b[1]:
			new = (min(a[0], b[0]), a[1])
			s.pop(-1)
			s.pop(-1)
			i -= 1
			s.append(new)
		else:
			ans.append(s[i])
			s.pop(-1)
			i -= 1
	ans.append(s[0])
	res = 0
	for i in range(len(ans)):
		cnt = ans[i][1] - ans[i][0]
		res += (cnt + 2) * (cnt + 1) // 2
	print(res)


def summ(n):
	return n * (n + 1) // 2
for _ in range(int(input())):
	n = int(input())
	k = list(map(int, input().split()))
	h = list(map(int, input().split()))
	s = []
	s.append([k[0], h[0]])
	for i in range(1, n):
		while len(s) > 0:
			prevtime = s[-1][0]
			prevh = s[-1][1]
			diff = k[i] - prevtime
			if diff >= h[i]:
				s.append([k[i], h[i]])
				break
			else:
				h[i] = max(h[i], diff + prevh)
				s.pop()
		if len(s) == 0:
			s.append([k[i], h[i]])
	ans = 0
	for i in range(len(s)):
		ans += summ(s[i][-1])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	ks = s.split()
	s = input()
	hs = s.split()
	arr = []
	for i in range(n):
		arr.append([int(ks[i]) - int(hs[i]) + 1, int(ks[i])])
	arr.sort()
	a = [arr[0][0], arr[0][1]]
	ans = 0
	for i in range(1, n):
		if arr[i][0] <= a[1]:
			a[1] = max(a[1], arr[i][1])
		else:
			x = a[1] - a[0] + 1
			ans += x * (x + 1) // 2
			a = [arr[i][0], arr[i][1]]
	x = a[1] - a[0] + 1
	ans += x * (x + 1) // 2
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	tm = list(map(int, input().split()))
	hm = list(map(int, input().split()))
	lstS = [tm[0] - hm[0] + 1]
	lstE = [tm[0]]
	for i in range(1, n):
		e = tm[i]
		s = tm[i] - hm[i] + 1
		if len(lstS) == 0:
			lstS.append(s)
			lstE.append(e)
		if len(lstS) != 0 and s <= lstE[-1]:
			while len(lstS) > 0 and s <= lstE[-1]:
				os = lstS.pop()
				lstE.pop()
				s = min(os, s)
			lstS.append(s)
			lstE.append(e)
		else:
			lstS.append(s)
			lstE.append(e)
	tot = 0
	for i in range(len(lstS)):
		rng = lstE[i] - lstS[i] + 1
		tot += rng * (rng + 1) // 2
	print(tot)


for t in range(int(input())):
	n = int(input())
	k = [int(i) for i in input().split()]
	h = [int(i) for i in input().split()]
	atleast = h[:]
	for i in range(n - 2, -1, -1):
		if k[i + 1] - k[i] < atleast[i + 1]:
			if atleast[i] < atleast[i + 1] - (k[i + 1] - k[i]):
				atleast[i] = atleast[i + 1] - (k[i + 1] - k[i])
	ans = atleast[0] * (atleast[0] + 1) // 2
	for i in range(1, n):
		ans += atleast[i] * (atleast[i] + 1) // 2
		if atleast[i] > k[i] - k[i - 1]:
			ans -= atleast[i] * (atleast[i] + 1) // 2
			ans -= atleast[i - 1] * (atleast[i - 1] + 1) // 2
			atleast[i] = atleast[i - 1] + k[i] - k[i - 1]
			ans += atleast[i] * (atleast[i] + 1) // 2
	print(ans)


for _ in range(int(input())):
	n = int(input())
	time = [int(x) for x in input().split()]
	damage = [int(x) for x in input().split()]
	biggesttime = n - 1
	biggestdamage = n - 1
	for j in range(n - 2, -1, -1):
		diffoftime = time[biggesttime] - time[j]
		if diffoftime >= damage[biggestdamage]:
			biggestdamage = j
			biggesttime = j
		elif diffoftime <= damage[biggestdamage] - damage[j]:
			damage[j] = 0
		else:
			damage[biggestdamage] = damage[j] + diffoftime
			damage[j] = 0
	s = 0
	for x in damage:
		if x != 0:
			s += x * (x + 1) // 2
	print(s)


def problemC(n, seconds, health):
	intervals = []
	for i in range(n):
		intervals.append((seconds[i] - health[i] + 1, seconds[i]))
	intervals.sort()
	(l, r) = (-1, -2)
	ans = 0
	for (left, right) in intervals:
		if left > r:
			ans += (r - l + 1) * (r - l + 2) // 2
			(l, r) = (left, right)
		else:
			r = max(r, right)
	ans += (r - l + 1) * (r - l + 2) // 2
	return ans
for _ in range(int(input())):
	n = int(input())
	seconds = list(map(int, input().split(' ')))
	health = list(map(int, input().split(' ')))
	print(problemC(n, seconds, health))


import math
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import copy
t = int(input())
for _ in range(t):
	n = int(input())
	k = [int(i) for i in input().split()]
	h = [int(i) for i in input().split()]
	(l, r) = (k[-1] - h[-1] + 1, k[-1])
	i = n - 2
	ans = 0
	while i >= 0:
		if k[i] < l:
			ans += (r - l + 1) * (r - l + 2) // 2
			l = k[i] - h[i] + 1
			r = k[i]
		else:
			l = min(l, k[i] - h[i] + 1)
		i -= 1
	ans += (r - l + 1) * (r - l + 2) // 2
	print(ans)


t = int(input())
while t:
	t -= 1
	n = int(input())
	k = list(map(int, input().split()))
	h = list(map(int, input().split()))
	l = -1
	r = -1
	res = 0
	for i in range(n - 1, -1, -1):
		if l == -1:
			r = k[i]
			l = k[i] - h[i] + 1
		elif k[i] < l:
			res += (r - l + 1) * (r - l + 2) // 2
			r = k[i]
			l = k[i] - h[i] + 1
		elif k[i] - h[i] + 1 < l:
			l = k[i] - h[i] + 1
	res += (r - l + 1) * (r - l + 2) // 2
	print(res)


def sum_till(n):
	return n * (n + 1) // 2
for _ in range(int(input())):
	n = int(input())
	arrivals = list(map(int, input().split()))
	healths = list(map(int, input().split()))
	intervals = []
	for (i, arrival) in enumerate(arrivals):
		this_r = arrival
		this_l = arrival - healths[i] + 1
		intervals.append((this_l, this_r))
	intervals.sort()
	merged_intervals = []
	(curr_l, curr_r) = (1, 0)
	ans = 0
	for (i, (l, r)) in enumerate(intervals):
		if l <= curr_r:
			curr_r = max(curr_r, r)
		else:
			merged_intervals.append((curr_l, curr_r))
			curr_l = l
			curr_r = r
	merged_intervals.append((curr_l, curr_r))
	for (l, r) in merged_intervals:
		ans += sum_till(r - l + 1)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	k = list(map(int, input().split()))
	h = list(map(int, input().split()))
	a = []
	for i in range(n - 1, -1, -1):
		a.append((k[i] - h[i] + 1, k[i]))
	a.sort()
	stack = []
	stack.append(a[0])
	for i in range(1, n):
		if stack[-1][1] >= a[i][0]:
			temp = stack.pop()
			stack.append((temp[0], max(a[i][1], temp[1])))
		else:
			stack.append(a[i])
	ans = 0
	for i in range(len(stack)):
		t = stack[i][1] - stack[i][0] + 1
		ans += t * (t + 1) // 2
	print(ans)


for t in range(int(input())):
	n = int(input())
	ls = list(map(int, input().strip().split()))
	lh = list(map(int, input().strip().split()))
	lis = []
	lis.append((ls[0] - lh[0] + 1, ls[0]))
	for i in range(1, n):
		a = ls[i] - lh[i] + 1
		if a <= lis[-1][1] and lis[-1][0] <= a:
			lis[-1] = (lis[-1][0], ls[i])
		elif lis[-1][0] > a:
			del lis[-1]
			while True:
				if len(lis) == 0:
					lis.append((a, ls[i]))
					break
				elif a <= lis[-1][1] and lis[-1][0] <= a:
					lis[-1] = (lis[-1][0], ls[i])
					break
				elif lis[-1][0] > a:
					del lis[-1]
				else:
					lis.append((a, ls[i]))
					break
		else:
			lis.append((a, ls[i]))
	co = 0
	for i in range(len(lis)):
		k = lis[i][1] - lis[i][0] + 1
		co += k * (k + 1) // 2
	print(co)


t = int(input())
for _ in range(t):
	n = int(input())
	ks = [int(x) for x in input().split()]
	hs = [int(x) for x in input().split()]
	dct = {}
	for i in range(n):
		dct[ks[i] - hs[i]] = max(dct.get(ks[i] - hs[i], -1), ks[i])
	ds = sorted(dct.keys())
	i = 0
	ans = 0
	while 1:
		right = dct[ds[i]]
		left = ds[i]
		while i < len(ds) and ds[i] < right:
			right = max(right, dct[ds[i]])
			i += 1
		ans += (right - left) * (right - left + 1) // 2
		if i == len(ds):
			break
	print(ans)


from re import L
from collections import deque
from collections import Counter
import sys
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = 0
	now = 0
	pre = 0
	for i in range(n - 2, -1, -1):
		diff = a[i + 1] - a[i]
		b[i] = max(b[i], b[i + 1] - diff)
	for (k, h) in zip(a, b):
		if k - pre >= h:
			ans += (1 + h) * h // 2
			now = h
		else:
			ans += (now + 1 + now + k - pre) * (k - pre) // 2
			now = now + k - pre
		pre = k
	print(ans)


for _ in range(int(input())):
	m = int(input())
	monsters = list(map(int, input().split()))
	health = list(map(int, input().split()))
	intervals = []
	for (idx, monster_location) in enumerate(monsters):
		intervals.append([monster_location - health[idx] + 1, monster_location])
	intervals.sort(key=lambda x: (x[0], x[1]))
	overlap = []
	(start, end) = intervals[0]
	for (next_start, next_end) in intervals[1:]:
		if next_start <= end:
			end = max(end, next_end)
		else:
			overlap.append([start, end])
			start = next_start
			end = next_end
	if not overlap or overlap[-1] != [start, end]:
		overlap.append([start, end])
	ans = 0
	for (start, end) in overlap:
		ans += (end - start + 1) * (end - start + 2) // 2
	print(ans)


def solve(n):
	return n * (n + 1) // 2
t = int(input())
for _ in range(t):
	n = int(input())
	app = list(map(int, input().split()))
	hea = list(map(int, input().split()))
	ran = []
	for i in range(n):
		r = app[i]
		l = app[i] - hea[i] + 1
		ran.append([l, r])
	ran.sort(key=lambda x: x[0])
	l = 1
	r = 0
	ans = 0
	for i in range(n):
		if ran[i][0] > r:
			ans += solve(r - l + 1)
			l = ran[i][0]
			r = ran[i][1]
		else:
			r = max(r, ran[i][1])
	ans += solve(r - l + 1)
	print(ans)


def sum_till(n):
	return n * (n + 1) // 2
for t in range(int(input())):
	n = int(input())
	k = list(map(int, input().split()))
	h = list(map(int, input().split()))
	if True:
		start = []
		end = []
		for i in range(1, n + 1):
			st = k[-i] - h[-i] + 1
			ed = k[-i]
			start.append(st)
			end.append(ed)
		mana = 0
		temp_st = start[0]
		temp_ed = end[0]
		diff = []
		for i in range(n - 1):
			temp_st = min(temp_st, start[i])
			temp_ed = max(temp_ed, end[i])
			if temp_st > end[i + 1]:
				diff.append(temp_ed - temp_st + 1)
				temp_st = start[i + 1]
				temp_ed = end[i + 1]
		temp_st = min(temp_st, start[n - 1])
		temp_ed = max(temp_ed, end[n - 1])
		diff.append(temp_ed - temp_st + 1)
		s = 0
		for i in diff:
			s += sum_till(i)
		print(s)


def sumN(X):
	return X * (X + 1) // 2
from math import inf
for t in range(int(input())):
	N = int(input())
	K = list(map(int, input().split()))
	H = list(map(int, input().split()))
	seg = list()
	for i in range(len(H)):
		seg.append((K[i] - H[i], K[i]))
	seg.sort()
	(l, r) = (-1, -1)
	ans = 0
	for i in seg:
		if i[0] >= r:
			ans += (r - l) * (r - l + 1) // 2
			(l, r) = tuple(i)
		else:
			r = max(r, i[1])
	ans += (r - l) * (r - l + 1) // 2
	print(ans)


t = int(input())
while t:
	n = int(input())
	lt = list(map(int, input().split()))
	lh = list(map(int, input().split()))
	li = []
	for i in range(n):
		li.append([lt[i] - lh[i] + 1, lt[i]])
	li.sort()
	i = 0
	ele = li[0]
	while ele[-1] != li[-1][-1]:
		if li[i + 1][0] <= li[i][1]:
			li[i] = [min(li[i][0], li[i + 1][0]), max(li[i + 1][1], li[i][1])]
			li.pop(i + 1)
		else:
			i += 1
		ele = li[i]
	s = 0
	for ele in li:
		s += (ele[-1] - ele[-2] + 1) * (ele[-1] - ele[-2] + 2) // 2
	print(int(s))
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	k = list(map(int, input().split()))
	h = list(map(int, input().split()))
	inter = []
	for i in range(n):
		inter.append([k[i] - h[i], k[i]])
	inter.sort()
	ans = 0
	s = -1
	e = -1
	for i in inter:
		if i[0] >= e:
			ans += (e - s) * (e - s + 1) // 2
			s = i[0]
			e = i[1]
		else:
			e = max(e, i[1])
	ans += (e - s) * (e - s + 1) // 2
	print(ans)


for _ in range(int(input())):
	n = int(input())
	k = list(map(int, input().split()))
	h = list(map(int, input().split()))
	arr = []
	for elem in range(n):
		arr.append([k[elem] - h[elem], k[elem]])
	arr.sort()
	(x, y) = (-1, -1)
	ans = 0
	for el in arr:
		if el[0] >= y:
			ans += (y - x) * (y - x + 1) // 2
			(x, y) = el
		else:
			y = max(y, el[1])
	ans += (y - x) * (y - x + 1) // 2
	print(ans)


T = int(input())

def calc(n):
	return (n + 1) * n // 2

def solve():
	n = int(input())
	k = list(map(int, input().split()))
	h = list(map(int, input().split()))
	ranges = []
	for i in range(n):
		ranges += [(k[i] - (h[i] - 1), k[i])]
	ranges = sorted(ranges)
	cur_l = ranges[0][0]
	cur_r = ranges[0][1]
	new_ranges = [(cur_l, cur_r)]
	for i in range(1, n):
		l = ranges[i][0]
		r = ranges[i][1]
		if l <= new_ranges[-1][1]:
			new_ranges[-1] = (new_ranges[-1][0], max(r, new_ranges[-1][1]))
		else:
			new_ranges += [(l, r)]
	answer = 0
	for i in range(len(new_ranges)):
		l = new_ranges[i][0]
		r = new_ranges[i][1]
		answer += calc(r - l + 1)
	return answer
for t in range(T):
	print(solve())


for _ in range(int(input())):
	n = int(input())
	time = list(map(int, input().split()))
	health = list(map(int, input().split()))
	ans = []
	for i in range(n):
		l = time[i]
		r = time[i] - health[i] + 1
		ans.append([r, l])

	def fun(x):
		return x * (x + 1) // 2
	arr = sorted(ans)
	ans = []
	val = 0
	for ele in arr:
		if not ans or ans[-1][-1] < ele[0]:
			if ans:
				l = ans[-1][0]
				r = ans[-1][1]
				val += fun(r - l + 1)
			ans.append(ele)
		else:
			ans[-1][-1] = max(ans[-1][-1], ele[1])
	(l, r) = (ans[-1][0], ans[-1][1])
	val += fun(r - l + 1)
	print(val)


def cal(a):
	return a * (a + 1) // 2
t = int(input())
for _ in range(t):
	n = int(input())
	k = [int(i) for i in input().split(' ')]
	h = [int(i) for i in input().split(' ')]
	stack = []
	ans = 0
	for i in range(n):
		origin = k[i] - h[i] + 1
		while stack:
			if stack[-1][0] <= origin and stack[-1][1] >= origin:
				origin = stack[-1][0]
				stack.pop()
				break
			elif stack[-1][1] < origin:
				break
			stack.pop()
		stack.append([origin, k[i]])
	for i in stack:
		ans += cal(i[1] - i[0] + 1)
	print(ans)


import io, os
import sys
import re
import math
from math import log2 as lg
from math import gcd
from decimal import *
from collections import deque
import random
import heapq
import itertools
const = 1000000007
ep = 1e-08

def get():
	return list(map(int, input().split()))
n = int(input())
for i in range(n):
	m = int(input())
	ends = get()
	monsters = get()
	intervals = []
	for j in range(m):
		(start, end) = (ends[j] - monsters[j] + 1, ends[j])
		intervals.append((start, end))
	intervals.sort(key=lambda x: x[0])
	merged = []
	(start, end) = (intervals[0][0], intervals[0][1])
	for j in range(1, m):
		if intervals[j][0] <= end:
			(start, end) = (min(start, intervals[j][0]), max(end, intervals[j][1]))
		else:
			merged.append((start, end))
			(start, end) = (intervals[j][0], intervals[j][1])
	merged.append((start, end))
	ans = 0
	for term in merged:
		gap = term[1] - term[0] + 1
		ans += gap * (gap + 1) // 2
	print(ans)


from collections import deque
for _ in range(int(input())):
	n = int(input())
	k = list(map(int, input().split()))
	h = list(map(int, input().split()))
	d = deque()
	res = 0
	for i in range(n):
		d.append((k[i] - h[i] + 1, k[i]))
	while len(d) != 0:
		if len(d) >= 2:
			(first, second) = (d[-2], d[-1])
			if first[1] >= second[0]:
				d.pop()
				d.pop()
				d.append((min(first[0], second[0]), second[1]))
				continue
		elem = d.pop()
		res += (elem[1] - elem[0] + 1) * (elem[1] - elem[0] + 2) // 2
	print(res)


import sys, collections

def solve(n, ts, ls):
	res = [0] * n
	for i in range(n):
		(t, l) = (ts[i], ls[i])
		if not i:
			res[i] = (1 + l) * l // 2
		elif ts[i - 1] < t - (l - 1):
			res[i] = res[i - 1] + (1 + l) * l // 2
		else:
			(jj, one) = (-1, t - l + 1)
			for j in range(i - 1, -1, -1):
				if ts[j] < one:
					jj = j
					break
				else:
					one = min(one, ts[j] - ls[j] + 1)
			cnt = t - one + 1
			cur = (1 + cnt) * cnt // 2
			if jj != -1:
				cur += res[jj]
			res[i] = cur
	return res[n - 1]
input = sys.stdin.readline
tests = int(input()[:-1])
for test in range(tests):
	n = int(input()[:-1])
	times = [int(s) for s in input()[:-1].split()]
	lives = [int(s) for s in input()[:-1].split()]
	print(solve(n, times, lives))


T = int(input())
while T > 0:
	T -= 1
	n = int(input())
	k = input().split()
	h = input().split()
	for i in range(n):
		k[i] = int(k[i])
	for i in range(n):
		h[i] = int(h[i])
	for i in range(n - 1, 0, -1):
		for j in range(i - 1, -1, -1):
			if h[i] - (k[i] - k[j]) > 0 and h[j] > h[i] - (k[i] - k[j]):
				h[i] = h[j] + (k[i] - k[j])
	sum = 0
	last = k[-1] + 10
	for i in range(n - 1, -1, -1):
		if k[i] <= last:
			a = int(h[i])
			b = int(h[i] + 1)
			if a % 2 == 0:
				a = int(a / 2)
			else:
				b = int(b / 2)
			sum += int(a * b)
			last = k[i] - h[i]
	print(sum)


import sys

def eprint(*args, **kwargs):
	print(*args, file=sys.stderr, **kwargs)
testcases = int(input())
for _ in range(testcases):
	_ = int(input())
	spawns = input().split()
	spawns = [int(x) for x in spawns]
	health = input().split()
	health = [int(x) for x in health]
	mana = 0
	monsters = list(zip(spawns, health))
	monsters.sort(key=lambda x: (x[0] - x[1], -x[1]))
	time = 0
	charging_since = 0
	for monster in monsters:
		start = monster[0] - monster[1]
		eprint('time is', time, 'monster:', monster, 'mana:', mana)
		if time > monster[0]:
			eprint('already killed that one')
			pass
		elif time > start:
			eprint('continuing to charge')
			mana += (monster[0] - charging_since) * (monster[0] - charging_since + 1) // 2 - (time - charging_since) * (time - charging_since + 1) // 2
			time = monster[0]
		else:
			eprint('starting to charge')
			mana += monster[1] * (monster[1] + 1) // 2
			time = monster[0]
			charging_since = start
	eprint(monsters)
	print(mana)


testcases = int(input())
for i in range(testcases):
	n_monster = int(input())
	input_1 = input().split()
	appear_list = list(map(int, input_1))
	input_2 = input().split()
	health_list = list(map(int, input_2))
	mana = int(0)
	for i in range(1, n_monster):
		for j in range(i):
			if appear_list[i] - health_list[i] < appear_list[j]:
				health_list[i] = max([health_list[j] + (appear_list[i] - appear_list[j]), health_list[i]])
				health_list[j] = 0
	for i in range(n_monster):
		mana = mana + health_list[i] * (health_list[i] + 1) // 2
	print(mana)


import sys
import collections
input = sys.stdin.readline
t = int(input().strip())

def merge(stk):
	for i in range(len(stk)):
		for j in range(i + 1, len(stk)):
			if stk[j][0] > stk[i][1] or stk[j][1] < stk[i][0]:
				continue
			else:
				stk[i] = (min(stk[i][0], stk[j][0]), max(stk[i][1], stk[j][1]))
				stk[j] = (min(stk[i][0], stk[j][0]), max(stk[i][1], stk[j][1]))
	return list(set(map(tuple, stk)))
for _ in range(t):
	n = int(input().strip())
	ks = list(map(int, input().split()))
	for i in range(len(ks)):
		ks[i] -= 1
	hs = list(map(int, input().split()))
	stk = []
	for i in range(len(ks)):
		l = ks[i] - hs[i] + 1
		r = ks[i]
		rng = (l, r)
		stk.append(rng)
	for i in range(1):
		stk = merge(stk)
	ret = 0
	while stk:
		rng = stk.pop()
		length = rng[1] - rng[0] + 1
		ret += length * (length + 1) // 2
	print(ret)