Chef Ada is building a new restaurant in the following way:
- First, $N$ points $X_1, X_2, \ldots, X_N$ are chosen on the $x$-axis.
- Then, $N$ columns (numbered $1$ through $N$) are made. For simplicity, the columns are represented as vertical segments; for each valid $i$, the height of the $i$-th segment is $H_i$.
- Ada assigns a column to each of the points $X_1, X_2, \ldots, X_N$ in an arbitrary way (each column must be assigned to exactly one point).
- Finally, Ada constructs the roof of the restaurant, represented by a polyline with $N$ vertices. Let's denote the column assigned to the $i$-th point by $P_i$. For each valid $i$, the $i$-th of these vertices is $(X_i, H_{P_i})$, i.e. the polyline joins the tops of the columns from left to right.
Ada wants the biggest restaurant. Help her choose the positions of the columns in such a way that the area below the roof is the biggest possible. Formally, she wants to maximise the area of the polygon whose perimeter is formed by the roof and the segments $(X_N, H_{P_N}) - (X_N, 0) - (X_1, 0) - (X_1, H_{P_1})$. Let $S$ be this maximum area; you should compute $2 \cdot S$ (it is guaranteed that $2 \cdot S$ is an integer).

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- $N$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $X_i$ and $H_i$.

-----Output-----
For each test case, print a single line containing one integer $2 \cdot S$.

-----Constraints-----
- $1 \le T \le 3 \cdot 10^5$
- $2 \le N \le 10^5$
- $0 \le X_1 < X_2 < \ldots < X_N \le 2 \cdot 10^9$
- $1 \le H_i \le 10^9$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $10^6$

-----Example Input-----
1
5
1 1
2 2
3 3
4 4
5 5

-----Example Output-----
27

-----Explanation-----

Source: codechef | Difficulty: HARD
Tags: Geometry

Sorting

Mathematics


Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	(x, p) = ([], [])
	for __ in range(n):
		line = list(map(int, input().split()))
		x.append(line[0])
		p.append(line[1])
	g = []
	for i in range(n - 1):
		g.append(x[i + 1] - x[i])
	bois = []
	bois.append(g[0])
	for k in range(n - 2):
		bois.append(g[k + 1] + g[k])
	bois.append(g[n - 2])
	bois.sort()
	p.sort()
	ans = 0
	for i in range(n):
		ans += p[i] * bois[i]
	print(ans)


for t in range(int(input())):
	n = int(input())
	height = []
	d = []
	prev = 0
	points = []
	nex = 0
	for i in range(n):
		(x, h) = [int(x) for x in input().split()]
		height.append(h)
		points.insert(i, x)
	for i in range(1, n):
		diff = points[i] - points[i - 1]
		d.append(diff)
	points = []
	for i in range(n - 1):
		num = d[i] + prev
		prev = d[i]
		points.append(num)
	points.append(d[n - 2])
	points.sort(reverse=True)
	height.sort(reverse=True)
	s = 0
	for i in range(n):
		s += height[i] * points[i]
	print(s)


for t in range(int(input())):
	n = int(input())
	h = []
	x = []
	for i in range(n):
		(a, b) = [int(j) for j in input().split()]
		h.append(b)
		x.append(a)
	last = x[0]
	y = [x[1] - x[0], x[n - 1] - x[n - 2]]
	for i in range(1, n - 1):
		y.append(-x[i - 1] + x[i + 1])
	y.sort()
	h.sort()
	ans = 0
	for i in range(n):
		ans += h[i] * y[i]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	xloli = []
	hloli = []
	d1 = []
	d2 = []
	for i in range(n):
		(x, h) = (int(x) for x in input().split())
		xloli.append(x)
		hloli.append(h)
	for i in range(1, n):
		d1.append(xloli[i] - xloli[i - 1])
	d2.append(d1[0])
	for i in range(n - 2):
		d2.append(d1[i + 1] + d1[i])
	d2.append(d1[-1])
	kaori = 0
	hloli.sort()
	d2.sort()
	for i in range(n):
		kaori += hloli[i] * d2[i]
	print(kaori)


for _ in range(int(input())):
	n = int(input())
	a = []
	g = []
	h = []
	I = list(map(int, input().split()))
	P = list(map(int, input().split()))
	a.append(I[0])
	a.append(P[0])
	h.append(I[1])
	h.append(P[1])
	g.append(a[1] - a[0])
	for i in range(2, n):
		L = list(map(int, input().split()))
		a.append(L[0])
		g.append(a[i] - a[i - 2])
		h.append(L[1])
	g.append(a[-1] - a[-2])
	g.sort()
	h.sort()
	var = 0
	for i in range(n):
		var += h[i] * g[i]
	print(var)


t = int(input(''))
for k in range(t):
	n = int(input(''))
	li = []
	li1 = []
	li2 = []
	for i in range(n):
		(p, q) = input().split()
		p = int(p)
		q = int(q)
		li.append(p)
		li1.append(q)
	r = li[1] - li[0]
	li2.append(r)
	for i in range(1, n - 1):
		p = li[i + 1] - li[i - 1]
		li2.append(p)
	li2.append(li[n - 1] - li[n - 2])
	li2.sort()
	li1.sort()
	ans = 0
	for i in range(n):
		ans = ans + li1[i] * li2[i]
	print(ans)


from itertools import chain
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(chain.from_iterable((map(int, input().split()) for _ in range(n))))
	b = [y - x for (x, y) in zip(a[::2], a[2::2])]
	b = sorted((x + y for (x, y) in zip([0] + b, b + [0])))
	c = sorted(a[1::2])
	print(sum((x * y for (x, y) in zip(b, c))))


for _ in range(int(input())):
	n = int(input())
	(x1, h1) = map(int, input().split())
	(x2, h2) = map(int, input().split())
	xi = [x2 - x1]
	hi = [h2, h1]
	for i in range(2, n):
		(x, h) = map(int, input().split())
		xi.append(x - x1)
		hi.append(h)
		x1 = x2
		x2 = x
	xi.append(x2 - x1)
	xi.sort()
	hi.sort()
	ans = 0
	for i in range(n):
		ans += xi[i] * hi[i]
	print(ans)


for i in range(int(input())):
	x = int(input())
	lb = []
	la = [0]
	h = []
	for j in range(x):
		(a, b) = map(int, input().split())
		lb.append(b)
		la.append(a)
		h.append(la[j + 1] - la[j])
	h.pop(0)
	la.pop(0)
	hnew = []
	for j in range(x - 2):
		hnew.append(h[j] + h[j + 1])
	hnew.append(la[1] - la[0])
	hnew.append(la[-1] - la[-2])
	hnew.sort()
	lb.sort()
	s = 0
	for j in range(x):
		s += lb[j] * hnew[j]
	print(s)


t = int(input())
for _ in range(t):
	n = int(input())
	(a, b) = ([], [])
	for _ in range(n):
		(x, h) = map(int, input().split())
		a.append(x)
		b.append(h)
	a = [y - x for (x, y) in zip(a, a[1:])]
	a = sorted((x + y for (x, y) in zip([0] + a, a + [0])))
	print(sum((x * y for (x, y) in zip(a, sorted(b)))))


t = int(input())
for x in range(t):
	n = int(input())
	xs = [0 for a in range(n)]
	hs = [0 for a in range(n)]
	for y in range(n):
		(xs[y], hs[y]) = map(int, input().split())
	xs.sort()
	hs.sort()
	curr = 2
	diffs = [xs[1] - xs[0], xs[n - 1] - xs[n - 2]]
	while curr < n:
		diffs.append(xs[curr] - xs[curr - 2])
		curr += 1
	diffs.sort()
	tot = 0
	for a in range(n):
		tot += diffs[a] * hs[a]
	print(tot)


t = int(input())
for q in range(t):
	n = int(input())
	(hght, points) = ([], [])
	for i in range(n):
		(x, h) = map(int, input().split())
		hght.append(h)
		points.append(x)
	points.sort()
	diff = []
	for i in range(1, n):
		diff.append(points[i] - points[i - 1])
	new_arr = [diff[0]]
	for i in range(1, n - 1):
		new_arr.append(diff[i - 1] + diff[i])
	new_arr.append(diff[-1])
	new_arr.sort()
	hght.sort()
	ans = 0
	for i in range(n):
		ans += new_arr[i] * hght[i]
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	xl = []
	hl = []
	for j in range(n):
		(x, h) = list(map(int, input().strip().split()))
		xl.append(x)
		hl.append(h)
	a = [0 for j in range(n)]
	a[0] = xl[1] - xl[0]
	for j in range(1, n - 1):
		a[j] = xl[j + 1] - xl[j - 1]
	a[n - 1] = xl[n - 1] - xl[n - 2]
	a.sort()
	hl.sort()
	sum = 0
	for j in range(n):
		sum += a[j] * hl[j]
	print(sum)


for _ in range(int(input())):
	n = int(input())
	x_arr = []
	h_arr = []
	d = []
	D = []
	for i in range(n):
		(x, y) = map(int, input().split())
		x_arr.append(x)
		h_arr.append(y)
	for x in range(1, n):
		d.append(x_arr[x] - x_arr[x - 1])
	D.append(d[0])
	for i in range(len(d) - 1):
		D.append(d[i] + d[i + 1])
	D.append(d[-1])
	h_arr.sort()
	D.sort()
	ans = 0
	for x in range(n):
		ans += D[x] * h_arr[x]
	print(ans)


t = int(input())
for op in range(t):
	n = int(input())
	x = []
	h = []
	for i in range(n):
		(a, b) = map(int, input().split())
		x.append(a)
		h.append(b)
	x.sort()
	x_diff = []
	for i in range(0, n - 2):
		x_diff.append(x[i + 2] - x[i])
	x_diff.append(x[1] - x[0])
	x_diff.append(x[n - 1] - x[n - 2])
	x_diff.sort()
	h.sort()
	area = 0
	for i in range(0, n):
		area += h[i] * x_diff[i]
	print(area)


for _ in range(int(input())):
	n = int(input())
	X = [0 for i in range(n)]
	H = [0 for i in range(n)]
	for i in range(n):
		(x, h) = map(int, input().split())
		X[i] = x
		H[i] = h
	X1 = [0 for i in range(n)]
	for i in range(n - 2):
		X1[i] = X[i + 2] - X[i]
	(X1[n - 2], X1[n - 1]) = (X[1] - X[0], X[n - 1] - X[n - 2])
	X1.sort()
	H.sort()
	res = 0
	for i in range(n):
		res += X1[i] * H[i]
	print(res)


for t in range(int(input())):
	x = []
	y = []
	z = []
	res = 0
	n = int(input(''))
	for i in range(n):
		(temp1, temp2) = input('').split()
		x.append(int(temp1))
		y.append(int(temp2))
	z.insert(0, x[1] - x[0])
	z.insert(-1, x[-1] - x[-2])
	for i in range(1, n - 1):
		z.insert(i, x[i + 1] - x[i - 1])
	y.sort(reverse=True)
	z.sort(reverse=True)
	for i in range(n):
		res = res + y[i] * z[i]
	print(res)


for _ in range(int(input())):
	n = int(input())
	x = []
	h = []
	gaps = []
	bois = []
	ans = 0
	for __ in range(n):
		q = list(map(int, input().split()))
		x.append(q[0])
		h.append(q[1])
	for i in range(1, n):
		gaps.append(x[i] - x[i - 1])
	bois.append(gaps[0])
	for i in range(1, n - 1):
		bois.append(gaps[i] + gaps[i - 1])
	bois.append(gaps[n - 2])
	bois.sort()
	h.sort()
	for i in range(n):
		ans += h[i] * bois[i]
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	(a, b) = ([], [])
	u = v = None
	for _ in range(n):
		(x, h) = map(int, input().split())
		if v is None:
			v = x
		if u is not None:
			a.append(x - u)
		u = v
		v = x
		b.append(h)
	a.append(x - u)
	print(sum((x * y for (x, y) in zip(sorted(a), sorted(b)))))


for _ in range(int(input())):
	n = int(input())
	arr = []
	height = []
	d = []
	final = []
	for i in range(n):
		(x, y) = map(int, input().split())
		arr.append(x)
		height.append(y)
	for x in range(1, n):
		d.append(arr[x] - arr[x - 1])
	final.append(d[0])
	for i in range(len(d) - 1):
		final.append(d[i] + d[i + 1])
	final.append(d[-1])
	height.sort()
	final.sort()
	ans = 0
	for x in range(n):
		ans += final[x] * height[x]
	print(ans)


testCase = int(input())
for t in range(testCase):
	n = int(input())
	xArray = []
	hArray = []
	for i in range(n):
		(x, h) = [int(y) for y in input().split()]
		xArray.append(x)
		hArray.append(h)
	wArray = []
	for i in range(1, len(xArray), 1):
		wArray.append(xArray[i] - xArray[i - 1])
	finalWArray = []
	finalWArray.append(wArray[0])
	for i in range(1, len(wArray), 1):
		finalWArray.append(wArray[i] + wArray[i - 1])
	finalWArray.append(wArray[len(wArray) - 1])
	finalWArray.sort(reverse=True)
	hArray.sort(reverse=True)
	area = 0
	for i in range(len(finalWArray)):
		area = area + hArray[i] * finalWArray[i]
	print(area)


for i in range(int(input())):
	n = int(input())
	arr1 = []
	arr2 = []
	for i in range(n):
		l = input().split()
		arr1.append(int(l[0]))
		arr2.append(int(l[1]))
	arr1.append(arr1[-1])
	arr1.insert(0, arr1[0])
	arr2.sort()
	base = []
	for i in range(1, n + 1):
		base.append(arr1[i + 1] - arr1[i - 1])
	base.sort()
	ans = 0
	for i in range(n):
		ans += base[i] * arr2[i]
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	(X, H) = ([0] * n, [0] * n)
	for i in range(n):
		(X[i], H[i]) = map(int, input().split())
	H.sort(reverse=True)
	L = [X[1] - X[0], X[n - 1] - X[n - 2]]
	for i in range(1, n - 1):
		L.append(X[i + 1] - X[i] + (X[i] - X[i - 1]))
	L.sort(reverse=True)
	area = 0
	for i in range(n):
		area += H[i] * L[i]
	print(area)


t = int(input())
for i in range(t):
	n = int(input())
	a = []
	b = []
	for j in range(n):
		(x, y) = map(int, input().split())
		a.append(x)
		b.append(y)
	b.sort()
	s = []
	s.append(a[1] - a[0])
	s.append(a[n - 1] - a[n - 2])
	for k in range(1, n - 1):
		s.append(a[k + 1] - a[k - 1])
	s.sort()
	ans = 0
	for z in range(n):
		ans += s[z] * b[z]
	print(ans)


from sys import stdin
t = int(stdin.readline())
while t:
	n = int(stdin.readline())
	diff_prev = 0
	(d, D) = ([], [])
	h = [0]
	(x_prev, h[0]) = [int(x) for x in stdin.readline().split()]
	for i in range(n - 1):
		(x, ht) = [int(x) for x in stdin.readline().split()]
		h.append(ht)
		d.append(x - x_prev)
		D.append(diff_prev + d[i])
		diff_prev = d[i]
		x_prev = x
	D.append(d[n - 2])
	D.sort()
	h.sort()
	ans = 0
	for i in range(n):
		ans += D[i] * h[i]
	print(ans)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	x = []
	p = []
	for j in range(n):
		(a, b) = map(int, input().split())
		x.append(a)
		p.append(b)
	differences = []
	for u in range(n - 1, 1, -1):
		differences.append(x[u] - x[u - 2])
	differences.append(x[-1] - x[-2])
	differences.append(x[1] - x[0])
	differences.sort()
	p.sort()
	answer = 0
	while len(differences) > 0:
		answer = answer + p.pop() * differences.pop()
	print(answer)


def find(X, H):
	if len(X) == 2:
		return (X[1] - X[0]) * sum(H)
	X = sorted(X)
	W = []
	for i in range(1, len(H) - 1):
		W += [X[i + 1] - X[i - 1]]
	W += [X[1] - X[0]]
	W += [X[-1] - X[-2]]
	W = sorted(W)
	H = sorted(H)
	return sum([W[i] * H[i] for i in range(len(W))])
for _ in range(int(input())):
	N = int(input())
	X = []
	H = []
	for i in range(N):
		(x, h) = list(map(int, input().strip().split()))
		X += [x]
		H += [h]
	print(find(X, H))


t = int(input())
for i in range(t):
	n = int(input())
	cols = []
	heights = []
	for i in range(n):
		(xi, hi) = list(map(int, input().split()))
		heights.append(hi)
		cols.append(xi)
	diff = [cols[1] - cols[0], cols[n - 1] - cols[n - 2]]
	for j in range(n - 2):
		diff.append(cols[j + 2] - cols[j])
	diff.sort()
	heights.sort()
	total = 0
	for j in range(n):
		total += diff[j] * heights[j]
	print(total)


from itertools import chain
t = int(input())
for _ in range(t):
	n = int(input())
	(a, b) = ([], [])
	for _ in range(n):
		(x, h) = map(int, input().split())
		a.append(x)
		b.append(h)
	a = [y - x for (x, y) in zip(a, a[1:])]
	a = sorted((x + y for (x, y) in zip([0] + a, a + [0])))
	print(sum((x * y for (x, y) in zip(a, sorted(b)))))


t = int(input())
for i in range(t):
	n = int(input())
	X = []
	H = []
	for i in range(n):
		(x, y) = map(int, input().split())
		X.append(x)
		H.append(y)
	H = sorted(H)
	a = []
	for i in range(1, n):
		a.append(X[i] - X[i - 1])
	b = []
	b.append(a[0])
	b.append(a[n - 2])
	for i in range(0, n - 2):
		b.append(a[i] + a[i + 1])
	b = sorted(b)
	ans = 0
	for i in range(n):
		ans += H[i] * b[i]
	print(ans)


t = int(input())
while t:
	dd = []
	l = []
	h = []
	pr = 0
	d = []
	n = int(input())
	for i in range(n):
		(x, hi) = map(int, input().split())
		l.append(x)
		h.append(hi)
	l.sort()
	for i in range(1, n):
		dd.append(l[i] - l[i - 1])
	d.append(dd[0])
	for i in range(1, n - 1):
		d.append(dd[i] + dd[i - 1])
	d.append(dd[-1])
	d.sort()
	h.sort()
	pr = 0
	for i in range(n):
		pr += d[i] * h[i]
	print(pr)
	t -= 1


t = int(input())
ans = []
for u in range(t):
	n = int(input())
	(x, h, gap) = ([], [], [])
	for i in range(n):
		l = list(map(int, input().split()))
		x.append(l[0])
		h.append(l[1])
		if i == 1:
			gap.append(x[1] - x[0])
		elif i > 1:
			gap.append(x[i] - x[i - 2])
	gap.append(x[n - 1] - x[n - 2])
	gap.sort()
	h.sort()
	ans.append(0)
	for j in range(n):
		ans[u] += h[j] * gap[j]
for a in ans:
	print(a)


t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	b = []
	for i in range(n):
		(x, y) = list(map(int, input().split()))
		a.append(x)
		b.append(y)
	b.sort()
	xcor = []
	xcor.append(a[1] - a[0])
	xcor.append(a[n - 1] - a[n - 2])
	for i in range(1, n - 1):
		xcor.append(a[i + 1] - a[i - 1])
	xcor.sort()
	ans = 0
	for i in range(n):
		ans = ans + xcor[i] * b[i]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	(l1, l2) = ([], [])
	(x1, h1) = map(int, input().split())
	(x2, h2) = map(int, input().split())
	l1 = [x2 - x1]
	l2 = [h1, h2]
	for i in range(2, n):
		(x, h) = map(int, input().split())
		l1.append(x - x1)
		l2.append(h)
		x1 = x2
		x2 = x
	l1.append(x2 - x1)
	l1.sort()
	l2.sort()
	a = 0
	for i in range(n):
		a += l1[i] * l2[i]
	print(a)


t = int(input())
for _ in range(t):
	n = int(input())
	x = []
	y = []
	for i in range(n):
		(_x, _y) = map(int, input().split())
		x.append(_x)
		y.append(_y)
	x.sort()
	y.sort()
	ans = 0
	if n > 2:
		inc_sum = [x[1] - x[0]]
		for i in range(1, n - 1):
			inc_sum.append(x[i + 1] - x[i - 1])
		inc_sum.append(x[n - 1] - x[n - 2])
		ind = list(range(n))
		ind.sort(key=lambda x: inc_sum[x])
		for i in range(n):
			ans += y[i] * inc_sum[ind[i]]
	else:
		ans = (y[0] + y[1]) * (x[1] - x[0])
	print(ans)


from collections import defaultdict
from heapq import *
import itertools, math

def parse_integer_list():
	return [int(x) for x in input().split()]

def handle_input(N, X, H):
	s = 0
	X.insert(0, X[0])
	X.append(X[-1])
	lengths = []
	for i in range(1, N + 1):
		lengths.append(X[i + 1] - X[i - 1])
	lengths.sort()
	H.sort()
	for i in range(N):
		s += H[i] * lengths[i]
	return s
T = int(input())
for i in range(T):
	N = int(input())
	X = []
	H = []
	for i in range(N):
		(x, h) = parse_integer_list()
		X.append(x)
		H.append(h)
	print(handle_input(N, X, H))


II = lambda : [int(x) for x in input().split()]

def get_weights(Xs):
	W = []
	for i in range(len(Xs)):
		x0 = Xs[i - 1] if i > 0 else Xs[i]
		x1 = Xs[i]
		x2 = Xs[i + 1] if i + 1 < len(Xs) else Xs[i]
		W.append(x1 - x0 + x2 - x1)
	return W
T = int(input())
for _ in range(T):
	N = int(input())
	points = [II() for _ in range(N)]
	Xs = [x for (x, y) in points]
	Ys = [y for (x, y) in points]
	Ws = get_weights(Xs)
	Ys.sort()
	Ws.sort()
	S = sum(map(lambda a: a[0] * a[1], zip(Ys, Ws)))
	print(S)


for _ in range(int(input())):
	n = int(input())
	X = []
	A = []
	Y = []
	Z = []
	for j in range(n):
		(x, a) = map(int, input().split())
		X.append(x)
		A.append(a)
	for j in range(n - 1):
		Y.append(X[j + 1] - X[j])
	A.sort()
	Z.append(Y[0])
	for j in range(n - 2):
		Z.append(Y[j] + Y[j + 1])
	Z.append(Y[-1])
	Z.sort()
	r = 0
	for i in range(n):
		r += Z[i] * A[i]
	print(r)


T = int(input())
t = 0
while t < T:
	t += 1
	N = int(input())
	(h, x) = (list(), list())
	for i in range(N):
		(a, b) = list(map(int, input().split()))
		h.append(b)
		x.append(a)
	v = []
	for i in range(N):
		v.append(x[min(i + 1, N - 1)] - x[max(i - 1, 0)])
	h.sort()
	v.sort()
	ans = 0
	for i in range(N):
		ans += h[i] * v[i]
	print(ans)


t = int(input())
while t:
	t -= 1
	n = int(input())
	x = []
	h = []
	for i in range(n):
		(xi, hi) = [int(i) for i in input().split()]
		x.append(xi)
		h.append(hi)
	diff = [x[1] - x[0], x[n - 1] - x[n - 2]]
	for i in range(1, n - 1):
		diff.append(x[i + 1] - x[i - 1])
	diff.sort()
	h.sort()
	ans = 0
	for i in range(n):
		ans += h[i] * diff[i]
	print(ans)


t = int(input())
for test in range(t):
	n = int(input())
	X = []
	H = []
	for i in range(n):
		(x, h) = [int(x) for x in input().split()]
		X.append(x)
		H.append(h)
	H.sort(reverse=True)
	mapping = [[x, 0, 0] for x in X]
	mapping[0][1] = X[1] - X[0]
	mapping[-1][1] = X[-1] - X[-2]
	for i in range(1, n - 1):
		mapping[i][1] = X[i + 1] - X[i - 1]
	mapping.sort(key=lambda x: x[1], reverse=True)
	for i in range(n):
		mapping[i][2] = H[i]
	mapping.sort(key=lambda x: x[0])
	answer = 0
	for i in range(1, n):
		answer += (mapping[i][0] - mapping[i - 1][0]) * (mapping[i][2] + mapping[i - 1][2])
	print(answer)