Chef has come to a 2 dimensional garden in which there are N points. Each point has coordinates (x, y), where x can either be 1 or 2 or 3. Chef will now choose every triplet of these N points and make a triangle from it. You need to tell the sum of areas of all the triangles the Chef makes.
Note that some of the triplets might not form proper triangles, and would end up as a line or a point (ie. degenerate), but that is fine because their area will be zero.

-----Input-----
- The first line contains a single integer T, the number of test cases. The description of each testcase follows.
- The first line of each test case contains an integer N denoting the number of points on the plane.
- The next N lines contain 2 space separated integers x and y denoting the coordinates of the points. 

-----Output-----
For each test case, output a single line containing the answer. Your answer will be considered correct if the absolute error is less than or equal to 10-2.

-----Constraints-----
- 1 ≤ T ≤ 20
- 1 ≤ N ≤ 2000
- 1 ≤ x ≤ 3
- 1 ≤ y ≤106
- All (x, y) pairs are distinct

-----Example-----
Input:
2
3
1 1
2 1
3 3
4
1 1
2 2
2 1
3 3

Output:
1.0
2.0

-----Explanation:-----
Test Case 1: There is only one triangle which has non-zero area, and it's area is 1, hence the output.
Test Case 2: Let the points be A(1,1), B(2,2), C(2,1), D(3,3). There are 3 non degenerate triangles possible. 

-  area ABC = 0.5
-  area BCD = 0.5
-  area ACD = 1
Total area = 2

Difficulty: MEDIUM_HARD
Tags: Geometry

Mathematics

Starter code:

Solutions:
class Node(object):
	start = None
	end = None

	def __init__(self, s, e):
		self.start = s
		self.end = e
nodes = []

def do_append(p, q):
	p_index = find_index(p)
	q_index = find_index(q)
	if p_index is None and q_index is None:
		nodes.append(Node(p, q))
		return
	elif q_index is None:
		if p_index < 0:
			nodes[abs(p_index) - 1].start = p
		nodes[abs(p_index) - 1].end = q
		last_node = len(nodes)
		while last_node > abs(p_index):
			last_node -= 1
			del nodes[last_node]
		normalize(abs(p_index) - 1)
		return
	elif p_index == -1:
		if q_index == -1:
			nodes.insert(0, Node(p, q))
			normalize(0)
			return
		else:
			nodes[0].start = p
			p_index = 1
	if p_index < 0:
		p_index += 1
	else:
		p_index -= 1
	if q_index < 0:
		q_index += 1
	else:
		q_index -= 1
	if p_index == q_index:
		if p_index <= 0 and nodes[abs(p_index)].start > p:
			nodes.insert(-1 * p_index, Node(p, q))
			normalize(abs(p_index))
	else:
		next_node = abs(p_index) + 1
		while next_node < abs(q_index):
			del nodes[abs(p_index) + 1]
			next_node += 1
		if p_index < 0:
			nodes[abs(p_index)].start = p
		if q_index < 0:
			nodes[abs(p_index)].end = q
		elif abs(q_index) != abs(p_index):
			new_end = nodes[abs(p_index) + 1].end
			del nodes[abs(p_index) + 1]
			nodes[abs(p_index)].end = new_end
		normalize(abs(p_index))

def normalize(index):
	again = False
	if index >= len(nodes) or index < 0:
		return
	if index > 0 and nodes[index - 1].end + 1 == nodes[index].start:
		nodes[index - 1].end = nodes[index].end
		del nodes[index]
		again = True
		if 1 < index < len(nodes) and nodes[index - 1].end + 1 == nodes[index].start:
			nodes[index - 1].end = nodes[index].end
			del nodes[index]
			again = True
	elif index + 1 < len(nodes) and nodes[index + 1].start - 1 == nodes[index].end:
		nodes[index].end = nodes[index + 1].end
		del nodes[index + 1]
		again = True
	if again:
		normalize(index)

def find_index(p, start_index=0):
	ind = start_index
	while ind < len(nodes):
		if nodes[ind].end >= p >= nodes[ind].start:
			return ind + 1
		elif nodes[ind].start > p:
			return -1 * (ind + 1)
		ind += 1
	return None
(n, l, r) = map(int, input().split())
lengths = list(map(int, input().split()))
lengths.sort()
i = 0
while i < n - 1:
	j = i + 1
	sums = lengths[i] + lengths[j]
	diff = abs(lengths[i] - lengths[j])
	if l > diff:
		start = l
	else:
		start = diff + 1
	if start < sums and start <= r:
		if sums <= r:
			end = sums - 1
		else:
			end = r
		if start <= end:
			do_append(start, end)
	i += 1
count = 0
for node in nodes:
	count = count + node.end - node.start + 1
print(count)


(N, L, R) = map(int, input().strip().split())
A = sorted(list(map(int, input().strip().split())))
res = 0
lef = 0
rig = 0
for i in range(N - 1):
	templ = A[N - 1 - i] - A[N - 2 - i] + 1
	tempr = A[N - 1 - i] + A[N - 2 - i] - 1
	if lef != 0 and tempr >= lef:
		lef = min(lef, templ)
	else:
		lef = max(lef, L)
		rig = min(rig, R)
		res += max(0, rig - lef + 1)
		lef = templ
		rig = tempr
lef = max(lef, L)
rig = min(rig, R)
res += max(0, rig - lef + 1)
print(res)


from operator import itemgetter
nlr = [int(i) for i in input().split()]
n = nlr[0]
l = nlr[1]
r = nlr[2]
inp_arr = [int(i) for i in input().split()]
inp_arr.sort()
i = 1
lo_up_arr = []
lo_up_arr.append([inp_arr[i] - inp_arr[i - 1], inp_arr[i] + inp_arr[i - 1]])
leng = 1

def fun(lo_up_arr, k, leng):
	i = leng - 1
	while i > k:
		if lo_up_arr[i] == []:
			i -= 1
			continue
		if lo_up_arr[i][0] >= lo_up_arr[k][0]:
			if lo_up_arr[i][0] > lo_up_arr[k][1]:
				f = 1
			elif lo_up_arr[i][1] <= lo_up_arr[k][1]:
				lo_up_arr[i] = []
			else:
				lo_up_arr[k][1] = lo_up_arr[i][1]
				lo_up_arr[i] = []
		elif lo_up_arr[i][1] < lo_up_arr[k][0]:
			f = 1
		elif lo_up_arr[i][1] > lo_up_arr[k][1]:
			lo_up_arr[k][0] = lo_up_arr[i][0]
			lo_up_arr[t][1] = lo_up_arr[i][1]
		else:
			lo_up_arr[k][0] = lo_up_arr[i][0]
		i -= 1
for i in range(2, n):
	flag = 0
	f = 1
	for t in range(0, leng):
		if lo_up_arr[t] == []:
			continue
		if inp_arr[i] - inp_arr[i - 1] >= lo_up_arr[t][0]:
			if inp_arr[i] - inp_arr[i - 1] > lo_up_arr[t][1]:
				flag = 0
				break
			elif inp_arr[i] + inp_arr[i - 1] <= lo_up_arr[t][1]:
				flag = 1
				f = 0
				break
			else:
				lo_up_arr[t][1] = inp_arr[i] + inp_arr[i - 1]
				flag = 1
				break
		elif inp_arr[i] + inp_arr[i - 1] < lo_up_arr[t][0]:
			flag = 0
			break
		elif inp_arr[i] + inp_arr[i - 1] > lo_up_arr[t][1]:
			lo_up_arr[t][0] = inp_arr[i] - inp_arr[i - 1]
			lo_up_arr[t][1] = inp_arr[i] + inp_arr[i - 1]
			flag = 1
			break
		else:
			lo_up_arr[t][0] = inp_arr[i] - inp_arr[i - 1]
			flag = 1
			break
	if flag:
		fun(lo_up_arr, t, leng)
	else:
		lo_up_arr.append([inp_arr[i] - inp_arr[i - 1], inp_arr[i] + inp_arr[i - 1]])
		leng += 1
i = 0
while i < leng:
	if lo_up_arr[i] == []:
		i += 1
		continue
	if lo_up_arr[i][1] > r:
		lo_up_arr[i][1] = r + 1
		if lo_up_arr[i][0] >= r:
			lo_up_arr[i][0] = r
		if lo_up_arr[i][0] < l:
			lo_up_arr[i][0] = l - 1
	elif lo_up_arr[i][0] < l:
		lo_up_arr[i][0] = l - 1
	i += 1
i = 0
res = 0
while i < leng:
	if lo_up_arr[i] == []:
		i += 1
		continue
	if not lo_up_arr[i][1] <= lo_up_arr[i][0]:
		res += lo_up_arr[i][1] - lo_up_arr[i][0] - 1
	i += 1
print(res)


def make_range(a):

	def modify(gg, rr):
		for x in range(len(rr)):
			if rr[x][1] < gg[0]:
				continue
			elif rr[x][0] > gg[0]:
				rr[x][0] = gg[0]
			rr[x][1] = gg[1]
			rr = rr[:x + 1]
			break
		return rr
	rr = []
	b = sorted(a)
	for i in range(1, len(b)):
		xx = [b[i] - b[i - 1] + 1, b[i] + b[i - 1] - 1]
		rr.append(xx)
		rr = modify(xx, rr)
	return rr
(n, l, r) = map(int, input().split())
a = map(int, input().split())
ran = make_range(a)
ans = 0
for x in ran:
	if l > x[1] or r < x[0]:
		continue
	else:
		ans += min(r, x[1]) - max(l, x[0]) + 1
print(ans)


(n, l, r) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
k = 0
lower = [0] * (n - 1)
upper = [0] * (n - 1)
for i in range(1, n):
	lower[k] = a[i] - a[i - 1] + 1
	upper[k] = a[i] + a[i - 1] - 1
	k += 1
sm = 0
i = 0
mn = float('inf')
mx = -1
low = l
while i < k:
	upperVal = 0
	lowerVal = 0
	if lower[i] <= mn and upper[i] >= mx:
		sm = 0
		low = l
	if lower[i] >= low and lower[i] <= r:
		lowerVal = lower[i]
	elif lower[i] < low and upper[i] >= low:
		lowerVal = low
	if upper[i] <= r and upper[i] >= low:
		low = upper[i] + 1
		upperVal = upper[i]
	elif upper[i] > r and lower[i] <= r:
		low = r + 1
		upperVal = r
	if lower[i] < mn:
		mn = lower[i]
	if upper[i] > mx:
		mx = upper[i]
	if upperVal != 0 and lowerVal != 0:
		sm += upperVal - lowerVal + 1
	i += 1
print(sm)


a = input()
b = input()
a = a.split()
a = [int(x) for x in a]
b = b.split()
b = [int(x) for x in b]
b.sort()
n = a[0]
l = a[1]
r = a[2]
mini = b[-1] - b[-2] + 1
for i in range(0, n - 1):
	if b[i + 1] - b[i] + 1 <= mini:
		mini = b[i + 1] - b[i] + 1
g = max(l, mini)
j = n - 1
while j > 0 and b[j] > r:
	j -= 1
maxi = b[j] + b[j - 1] - 1
c = min(r, maxi)
print(max(0, c - g + 1))


(n, L, R) = map(int, input().split())
ar = list(sorted(map(int, input().split())))
vec = []
for i in range(1, n):
	vec.append((max(L - 1, ar[i] - ar[i - 1]), min(R + 1, ar[i] + ar[i - 1])))
vec.sort()
vec.append((1e+20, 1e+20))
ans = 0
i = 0
while i < n - 1:
	st = vec[i][0]
	en = vec[i][1]
	i += 1
	while i < n - 1 and vec[i][0] < en:
		en = max(en, vec[i][1])
		i += 1
	if st < en:
		ans += en - st - 1
print(ans)


import numpy
import math
(n, l, r) = map(numpy.int64, input().split())
a = list(map(numpy.int64, input().split()))
ans = []
a.sort()
for i in range(1, n):
	Range = [max(l, a[i] - a[i - 1] + 1), min(r, a[i] + a[i - 1] - 1)]
	if Range[0] > Range[1]:
		continue
	ans.append([Range[0], Range[1]])
arr = []
for elem in ans:
	if elem[0] > elem[1]:
		continue
	arr.append([elem[0], 0])
	arr.append([elem[1], 1])
arr.sort()
cnt = 0
final_ans = 0
for elem in arr:
	if cnt == 0:
		start = elem[0]
	if elem[1] == 0:
		cnt += 1
	else:
		cnt -= 1
	if cnt == 0:
		final_ans = final_ans + (elem[0] - start + 1)
print(final_ans)


from itertools import chain
flatten = chain.from_iterable
(LEFT, RIGHT) = (1, -1)

def join_ranges(data, offset=0):
	data = sorted(flatten((((start, LEFT), (stop + offset, RIGHT)) for (start, stop) in data)))
	c = 0
	for (value, label) in data:
		if c == 0:
			x = value
		c += label
		if c == 0:
			yield (x, value - offset)
(n, l, r) = map(int, input().split())
lis = list(map(int, input().split()))
lis.sort()
d = []
for i in range(n - 1):
	j = i + 1
	mini = abs(lis[j] - lis[i]) + 1
	maxi = lis[i] + lis[j] - 1
	d.append([mini, maxi + 1])
sol = list(join_ranges(d))
ans = 0
for i in sol:
	mini = max(l, i[0])
	maxi = min(r, i[1] - 1)
	if mini <= maxi:
		ans += maxi - mini + 1
print(ans)


import sys

def merge(arr, brr, p, q, r):
	(a, b) = (q - p + 1, r - q)
	ma1 = [arr[i + p] for i in range(0, a)]
	ma2 = [arr[i + q + 1] for i in range(0, b)]
	mb1 = [brr[i + p] for i in range(0, a)]
	mb2 = [brr[i + q + 1] for i in range(0, b)]
	(j, k, i) = (0, p, 0)
	while True:
		if ma1[i] <= ma2[j]:
			arr[k] = ma1[i]
			brr[k] = mb1[i]
			k += 1
			i += 1
		else:
			arr[k] = ma2[j]
			brr[k] = mb2[j]
			k += 1
			j += 1
		if i >= a or j >= b:
			break
	if i >= a:
		while j < b:
			arr[k] = ma2[j]
			brr[k] = mb2[j]
			k += 1
			j += 1
	elif j >= b:
		while i < a:
			arr[k] = ma1[i]
			brr[k] = mb1[i]
			k += 1
			i += 1

def merge_sort(arr, brr, p, q):
	if p < q:
		r = p + int((q - p) // 2)
		merge_sort(arr, brr, p, r)
		merge_sort(arr, brr, r + 1, q)
		merge(arr, brr, p, r, q)

def inter(arr, brr, i, l, r):
	if brr[i] < l or arr[i] > r:
		arr[i] = brr[i] = 0
	elif arr[i] <= l and r <= brr[i]:
		arr[i] = l
		brr[i] = r
	elif l <= arr[i] and brr[i] <= r:
		return
	elif arr[i] <= l and brr[i] <= r:
		arr[i] = l
	elif l <= arr[i] and r <= brr[i]:
		brr[i] = r

def union(arr, brr):
	mx = brr[0]
	for i in range(0, len(arr) - 1):
		if arr[i + 1] <= mx:
			arr[i + 1] = mx + 1
		mx = max(mx, brr[i + 1])
	ans = 0
	for i in range(0, len(arr)):
		if arr[i] <= brr[i] and arr[i] != 0:
			ans += brr[i] - arr[i] + 1
	return ans
inp = [int(i) for i in input().split()]
(n, l, r) = (inp[0], inp[1], inp[2])
inp = [int(i) for i in input().split()]
inp.sort()
arr = [inp[i] - inp[i - 1] + 1 for i in range(1, n)]
brr = [inp[i] + inp[i - 1] - 1 for i in range(1, n)]
for i in range(0, n - 1):
	inter(arr, brr, i, l, r)
merge_sort(arr, brr, 0, len(arr) - 1)
print(union(arr, brr))


import bisect
for _ in range(int(input())):
	n = int(input())
	(x1, x2, x3) = ([], [], [])
	for i in range(n):
		(x, y) = list(map(int, input().split()))
		if x == 1:
			x1.append(y)
		if x == 2:
			x2.append(y)
		if x == 3:
			x3.append(y)
	x1.sort()
	x2.sort()
	x3.sort()
	(y1, y2, y3) = (len(x1), len(x2), len(x3))
	area = 0
	for i in range(y1):
		for j in range(i + 1, y1):
			area += abs(x1[i] - x1[j]) * (y2 + 2 * y3)
	for i in range(y3):
		for j in range(i + 1, y3):
			area += abs(x3[i] - x3[j]) * (y2 + 2 * y1)
	for i in range(y2):
		for j in range(i + 1, y2):
			area += abs(x2[i] - x2[j]) * (y1 + y3)
	area /= 2
	s1 = [0]
	for i in range(y2):
		s1.append(s1[-1] + x2[i])
	s2 = [0]
	for i in range(y2):
		s2.append(s2[-1] + x2[y2 - 1 - i])
	for i in x1:
		for j in x3:
			p1 = (i + j) / 2
			p = bisect.bisect_left(x2, p1)
			l = p
			h = y2 - l
			area += p1 * l - s1[l]
			area += s2[h] - p1 * h
	print(format(area, 'f'))


def lrval(l1, r1, l2, r2):
	l3 = max(l1, l2)
	r3 = min(r1, r2)
	if r3 < l3:
		return None
	return (l3, r3)
(n, l, r) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
b = []
for i in range(n - 1):
	diff = a[i + 1] - a[i] + 1
	sum1 = a[i + 1] + a[i] - 1
	if lrval(l, r, diff, sum1) != None:
		b.append(lrval(l, r, diff, sum1))
b.sort()
sum2 = b[0][1] - b[0][0] + 1
e = b[0][1]
for i in range(1, len(b)):
	if e >= b[i][1]:
		continue
	elif e < b[i][0]:
		sum2 = sum2 + b[i][1] - b[i][0] + 1
	elif e < b[i][1]:
		sum2 = sum2 + b[i][1] - e
	e = b[i][1]
print(sum2)


(n, left, right) = map(int, input().split())
a = list(map(int, input().split()))
if n <= 100:
	s = set()
	for i in range(0, n):
		for j in range(i + 1, n):
			for k in range(abs(a[i] - a[j]) + 1, a[i] + a[j]):
				if left <= k and k <= right:
					s.add(k)
	print(len(s))
else:
	a = sorted(a, reverse=True)
	ranges = []
	union = []
	for i in range(0, n - 1):
		j = i + 1
		ranges.append([max(left, abs(a[i] - a[j]) + 1), min(right, a[i] + a[j] - 1)])
	for (begin, end) in sorted(ranges):
		if union and union[-1][1] >= begin - 1:
			union[-1][1] = max(union[-1][1], end)
		else:
			union.append([begin, end])
	print(union[0][1] - union[0][0] + 1)


def read(type=int):
	return type(input())

def read_arr(type=int):
	return [type(token) for token in input().split()]

def cmp_to_key(cmp):
	from functools import total_ordering

	@total_ordering
	class K(object):

		def __init__(self, obj, *args):
			self.obj = obj

		def __lt__(self, other):
			return cmp(self.obj, other.obj) < 0

		def __eq__(self, other):
			return cmp(self.obj, other.obj) == 0
	return K

def cmp(i, j):
	if i[0] < j[0] or (i[0] == j[0] and i[1] < j[1]):
		return -1
	elif i[0] > j[0] or (i[0] == j[0] and i[1] > j[1]):
		return 1
	else:
		return 0

def merge(I):
	I.sort(key=cmp_to_key(cmp))
	J = []
	for i in I:
		if len(J) == 0 or J[-1][1] < i[0]:
			J.append(i)
		else:
			J[-1][1] = max(i[1], J[-1][1])
	return J

def merged_len(i):
	return max(0, min(i[1], R) - max(i[0], L) + 1)

def intersect(I):
	s = 0
	for i in I:
		s += merged_len(i)
	return s

def sol():
	A.sort()
	I = []
	for i in range(1, n):
		r = [A[i] - A[i - 1] + 1, A[i] + A[i - 1] - 1]
		I.append(r)
	I = merge(I)
	s = intersect(I)
	return s

def sol2():
	I = []
	for i in range(n):
		for j in range(i + 1, n):
			I.append([abs(A[i] - A[j]) + 1, A[i] + A[j] - 1])
	I = merge(I)
	s = intersect(I)
	return s
(n, L, R) = read_arr()
A = read_arr()
print(sol())


(n, l, r) = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
brr = [0] * (n - 1)
for i in range(n - 1):
	brr[i] = (arr[i + 1] - arr[i], arr[i + 1] + arr[i])
brr.sort(key=lambda x: x[1])
(le, ri) = (brr[n - 2][0] + 1, brr[n - 2][1] - 1)
count = 0
for i in range(n - 3, -1, -1):
	(a, b) = (brr[i][0] + 1, brr[i][1] - 1)
	if a > b:
		continue
	if le <= b:
		le = min(a, le)
	elif le > r or ri < l:
		(le, ri) = (a, b)
	else:
		(tl, tr) = (max(l, le), min(r, ri))
		count += tr - tl + 1
		(le, ri) = (a, b)
(tl, tr) = (max(l, le), min(r, ri))
count += tr - tl + 1
print(count)


(n, l, r) = map(int, input().split())
z = list(map(int, input().split()))
z.sort()
ans = 0
a = []
for i in range(1, n):
	q = max(z[i] - z[i - 1] + 1, l)
	m = min(z[i] + z[i - 1] - 1, r)
	if q <= r and m >= l:
		a.append([q, m])
b = []
for (begin, end) in sorted(a):
	if b and b[-1][1] >= begin - 1:
		b[-1][1] = max(b[-1][1], end)
	else:
		b.append([begin, end])
for i in b:
	ans = ans + (i[1] - i[0] + 1)
print(ans)


import time
(a, b, c) = list(map(int, input().split()))
d = list(map(int, input().split()))
d.sort()
max = []
min = []
d.reverse()
for i in range(a - 1):
	max.append([d[i] + d[i + 1] - 1, d[i] - d[i + 1] + 1])
uppr = c
clwr = b
total = 0
for i in range(len(max)):
	if max[i][0] >= uppr:
		if max[i][1] >= clwr and max[i][1] <= uppr:
			total += uppr - max[i][1] + 1
			uppr = max[i][1] - 1
	if max[i][0] < uppr:
		if max[i][1] >= clwr:
			total += max[i][0] - max[i][1] + 1
			uppr = max[i][1] - 1
		if max[i][1] < clwr:
			total += max[i][0] - clwr + 1
			break
time.sleep(1)
print(total)


(n, l, r) = input().split(' ')
(n, l, r) = [int(n), int(l), int(r)]
arr = [int(temp) for temp in input().strip().split(' ')]
arr.sort()
co = 0
for i in range(1, n):
	j = n - i
	ll = arr[j] - arr[j - 1] + 1
	rr = arr[j] + arr[j - 1] - 1
	if l <= ll <= r:
		if l <= rr <= r:
			co += rr - ll + 1
		else:
			co += r - ll + 1
		r = ll - 1
	elif l <= rr <= r:
		co += rr - l + 1
		break
print(co)


(N, L, R) = [int(n) for n in input().split()]
nums = [int(n) for n in input().split()]
nums.sort()
nums = [[nums[i + 1] - nums[i] + 1, nums[i + 1] + nums[i] - 1] for i in range(len(nums) - 1)]

def getIntersection(lst):
	(mn, mx) = lst
	shouldBeZero = False
	if mn > R:
		return None
	if mx < L:
		return None
	return (max(mn, L), min(mx, R))

def getNumsInRange(lst):
	if lst is None:
		return 0
	(mn, mx) = lst
	return mx - mn + 1

def getUnions(a):
	a.sort()
	b = [a[0]]
	for (begin, end) in a[1:]:
		if b and b[-1][1] >= begin - 1:
			b[-1][1] = max(b[-1][1], end)
		else:
			b.append([begin, end])
	return b
unions = getUnions(nums)
diffs = [getNumsInRange(getIntersection(num)) for num in unions]
print(sum(diffs))


(n, l, r) = map(int, input().split())
a = []
a.extend(map(int, input().split()))
a.sort()
b = []
c = 0
for i in range(n - 1):
	left = a[i + 1] - a[i] + 1
	right = a[i] + a[i + 1] - 1
	if left < l:
		left = l
	if right > r:
		right = r
	if right >= left:
		b.append((left, right))
		c += 1
b.sort()
s = b[0][1] - b[0][0] + 1
p = 0
for i in range(1, c):
	if b[i][0] > b[p][1]:
		s += b[i][1] - b[i][0] + 1
		p = i
	elif b[i][1] > b[p][1]:
		s += b[i][1] - b[p][1]
		p = i
print(s)


c = 1
cases = 1
while c <= cases:
	[n, l, r] = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	a.sort(reverse=True)
	pos = []
	for i in range(0, len(a) - 1):
		new = False
		if a[i] + a[i + 1] - 1 <= r and a[i] - a[i + 1] + 1 >= l:
			l1 = a[i] - a[i + 1] + 1
			r1 = a[i] + a[i + 1] - 1
			new = True
		elif a[i] + a[i + 1] - 1 > r and a[i] - a[i + 1] + 1 >= l and (a[i] - a[i + 1] + 1 < r):
			l1 = a[i] - a[i + 1] + 1
			r1 = r
			new = True
		elif a[i] - a[i + 1] + 1 < l and a[i] + a[i + 1] - 1 <= r and (a[i] + a[i + 1] - 1 > l):
			l1 = l
			r1 = a[i] + a[i + 1] - 1
			new = True
		elif a[i] - a[i + 1] + 1 < l and a[i] + a[i + 1] - 1 > r:
			l1 = l
			r1 = r
			new = True
		if len(pos) == 0 and new:
			pos.append((l1, r1))
		elif new and r1 >= pos[-1][0]:
			temp = pos.pop()
			pos.append((min(temp[0], l1), temp[1]))
		elif new:
			pos.append((l1, r1))
	ans = 0
	for i in pos:
		ans += i[1] - i[0] + 1
	print(ans)
	c = c + 1


(x1, l, r) = map(int, input().split())
a = sorted(list(map(int, input().split())))
e = len(a)
for i in range(e - 1, 0, -1):
	if a[i] <= r:
		w = min(a[i] + a[i - 1] - 1, r)
		break
t = l
x = a[-1] + a[-2] - 1
for i in range(e - 1):
	x = min(x, a[i + 1] - a[i] + 1)
	x = max(l, x)
print(max(0, w - x + 1))


(n, l, r) = map(int, input().split())
lis = list(map(int, input().split()))
lis.sort()
s = []
e = []
for i in range(n - 1):
	s.append(1 + lis[i + 1] - lis[i])
	e.append(lis[i + 1] + lis[i] - 1)
low = r + 1
ans = 0
i = n - 2
while i >= 0:
	if s[i] > r or e[i] < l:
		i -= 1
		continue
	s[i] = max(l, s[i])
	e[i] = min(r, e[i])
	if e[i] < low:
		ans += 1 + e[i] - s[i]
		low = s[i]
	elif s[i] < low:
		ans += low - s[i]
		low = s[i]
	i -= 1
print(ans)


(n, l, r) = list(map(int, input().split()))
strands = list(map(int, input().split()))
strands.sort()
range_list = []

def insert_into_list(left, right):
	range_list.append([left, right])
for i in range(n - 1, 0, -1):
	a = strands[i - 1]
	b = strands[i]
	left_range = b - a + 1
	right_range = a + b - 1
	if left_range < l:
		if right_range < l:
			continue
		left_range = l
	if right_range > r:
		if left_range > r:
			continue
		right_range = r
	insert_into_list(left_range, right_range)
range_list.sort()
sanitized_list = []
for i in range(len(range_list)):
	curr = range_list[i]
	curr_l = curr[0]
	curr_r = curr[1]
	if len(sanitized_list) == 0:
		sanitized_list.append(curr)
		continue
	last = sanitized_list[-1]
	last_l = last[0]
	last_r = last[1]
	if curr_l <= last_r:
		if curr_r > last_r:
			sanitized_list[-1][1] = curr_r
	else:
		sanitized_list.append(curr)
count = 0
for i in range(len(sanitized_list)):
	san_curr = sanitized_list[i]
	count += san_curr[1] - san_curr[0] + 1
print(count)


def mrg(arr, r, brr, r2, left, mid, right):
	last = mid - 1
	temp = left
	ln = right - left + 1
	while left <= last and mid <= right:
		if arr[left] <= arr[mid]:
			r[temp] = arr[left]
			r2[temp] = brr[left]
			temp = temp + 1
			left = left + 1
		else:
			r[temp] = arr[mid]
			r2[temp] = brr[mid]
			temp = temp + 1
			mid = mid + 1
	while left <= last:
		r[temp] = arr[left]
		r2[temp] = brr[left]
		temp = temp + 1
		left = left + 1
	while mid <= right:
		r[temp] = arr[mid]
		r2[temp] = brr[mid]
		mid = mid + 1
		temp = temp + 1
	i = 0
	while i < ln:
		arr[right] = r[right]
		brr[right] = r2[right]
		right = right - 1
		i += 1
	return

def merge_srt(arr, r, brr, r2, left, right):
	if right > left:
		mid = int((right + left) // 2)
		merge_srt(arr, r, brr, r2, left, mid)
		merge_srt(arr, r, brr, r2, mid + 1, right)
		mrg(arr, r, brr, r2, left, mid + 1, right)
	return
arr = [int(i) for i in input().split()]
n = arr[0]
l = arr[1]
r = arr[2]
arr = [int(i) for i in input().split()]
arr.sort()
arr1 = [0 for i in range(0, len(arr))]
arr2 = [0 for i in range(0, len(arr))]
for i in range(1, len(arr)):
	arr1[i - 1] = arr[i] - arr[i - 1] + 1
	arr2[i - 1] = arr[i] + arr[i - 1] - 1
for i in range(0, len(arr)):
	if arr1[i] < l and arr2[i] < l:
		arr1[i] = arr2[i] = 0
	elif arr1[i] > r and arr2[i] > r:
		arr1[i] = arr2[i] = 0
	elif arr1[i] < l and arr2[i] > r:
		arr1[i] = l
		arr2[i] = r
	elif arr1[i] < l and arr2[i] <= r:
		arr1[i] = l
	elif arr1[i] >= l and arr2[i] > r:
		arr2[i] = r
r1 = [0 for i in range(0, len(arr))]
r2 = [0 for i in range(0, len(arr))]
merge_srt(arr1, r1, arr2, r2, 0, len(arr) - 1)
mx = arr2[0]
for i in range(0, len(arr) - 1):
	if arr1[i + 1] <= mx:
		arr1[i + 1] = mx + 1
	if mx < arr2[i + 1]:
		mx = arr2[i + 1]
ans = 0
for i in range(0, len(arr)):
	if arr2[i] >= arr1[i] and arr1[i] >= l and (arr2[i] <= r):
		ans = ans + arr2[i] - arr1[i] + 1
print(ans)


(num_strands, L, R) = [int(i) for i in input().strip().split()]
strands = [int(i) for i in input().strip().split()]
strands.sort()
prev_shortest = 10 ** 18
total = 0
for i in range(num_strands - 1, 0, -1):
	longest = min(R + 1, strands[i] + strands[i - 1], prev_shortest)
	shortest = max(L, strands[i] - strands[i - 1] + 1)
	prev_shortest = min(prev_shortest, shortest)
	if longest - shortest >= 0:
		total += longest - shortest
print(total)


def intersection(L1, R1, L2, R2):
	return max(min(R1, R2) - max(L1, L2) + 1, 0)
(N, L, R) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
s = 0
mi = A[1] - A[0] + 1
(pl, pr) = (0, 0)
for i in range(2, N):
	d = A[i] - A[i - 1] + 1
	t = A[i - 1] + A[i - 2] - 1
	if d <= t:
		mi = min(mi, d)
	else:
		if mi < pl:
			s += intersection(L, R, mi, pl - 1)
		s += intersection(L, R, max(mi, pr + 1), t)
		(pl, pr) = (mi, t)
		mi = d
t = A[-1] + A[-2] - 1
if mi < pl:
	s += intersection(L, R, mi, pl - 1)
s += intersection(L, R, max(mi, pr + 1), t)
print(s)


def compute(a, b, l, r):
	if l > a:
		a = l
	if r < b:
		b = r
	if b >= a:
		return b - a + 1
	else:
		return 0
(n, l, r) = map(int, input().strip(' ').split(' '))
array = list(map(int, input().strip(' ').split(' ')))
array.sort()
comparelist = list()
for i in range(n - 1):
	comparelist.append((array[i + 1] - array[i] + 1, array[i + 1] + array[i] - 1))
import operator
comparelist.sort(key=operator.itemgetter(0))
count = 0
l1 = comparelist[0][0]
r1 = comparelist[0][1]
for i in range(1, n - 1):
	l2 = comparelist[i][0]
	r2 = comparelist[i][1]
	if r1 < l2:
		count += compute(l1, r1, l, r)
		l1 = l2
		r1 = r2
	elif r1 < r2:
		r1 = r2
count += compute(l1, r1, l, r)
print(count)


(N, L, R) = [int(x) for x in input().strip().split()]
S = [int(x) for x in input().strip().split()]
S = sorted(S)
mini = 10 ** 20
ran = []
for i in range(1, N):
	if S[i] - S[i - 1] < mini or (S[i] - S[i - 1] == mini and S[i] + S[i - 1] - 1 > ran[0][1]):
		mini = S[i] - S[i - 1]
		ran = [[S[i] - S[i - 1] + 1, S[i] + S[i - 1] - 1]]
if ran[0][1] >= S[-1] - S[-2] + 1:
	ran[0][1] = max(ran[0][1], S[-1] + S[-2] - 1)
else:
	ran.append([S[-1] - S[-2] + 1, S[-1] + S[-2] - 1])
cnt = 0
for interval in ran:
	if L <= interval[0] <= interval[1] <= R:
		cnt += interval[1] - interval[0] + 1
	elif interval[0] < L and L <= interval[1] <= R:
		cnt += interval[1] - L + 1
	elif L <= interval[0] <= R and interval[1] > R:
		cnt += R - interval[0] + 1
	elif interval[0] <= L < R <= interval[1]:
		cnt = R - L + 1
print(cnt)


class Node(object):
	start = None
	end = None

	def __init__(self, s, e):
		self.start = s
		self.end = e

def compare(x, y):
	a = x.end - x.start
	b = y.end - x.start
	if a < b:
		return -1
	elif a > b:
		return 1
	else:
		return 0
nodes = []
(n, l, r) = map(int, input().split())
lengths = list(map(int, input().split()))
lengths.sort()
i = 0
while i < n - 1:
	nodes.append(Node(lengths[i], lengths[i + 1]))
	i += 1
nodes = sorted(nodes, key=lambda k: k.end - k.start)
count = 0
for node in nodes:
	sums = node.start + node.end - 1
	if sums >= l:
		end = min(r, sums)
		start = max(node.end - node.start + 1, l)
		if start <= end:
			count += end - start + 1
			l = end + 1
print(count)


import sys

def main():
	(N, L, R) = map(int, sys.stdin.readline().split())
	strands = list(map(int, sys.stdin.readline().split()))
	strands.sort()
	stack = []
	for i in range(1, N):
		lower = strands[i] - strands[i - 1] + 1
		upper = strands[i] + strands[i - 1] - 1
		while stack:
			(s_lower, s_upper) = stack.pop()
			if lower >= s_lower:
				if lower <= s_upper + 1:
					lower = s_lower
				else:
					stack.append((s_lower, s_upper))
				break
		stack.append((lower, upper))
	ans = 0
	for (l, u) in stack:
		if l <= R:
			if l >= L:
				if u <= R:
					ans += u - l + 1
				else:
					ans += R - l + 1
			elif u <= R:
				ans += u - L + 1
			else:
				ans += R - L + 1
		else:
			break
	print(ans)
main()


(n, l, r) = map(int, input().strip().split())
A = list(map(int, input().strip().split()))
A.sort()
ans = 0
(p, q) = (r + 1, r + 1)
ans = 0
for i in range(n - 1, 0, -1):
	(a, b) = (A[i - 1], A[i])
	(x, y) = (b - a + 1, a + b - 1)
	if p == l:
		break
	if x < p:
		y = min(y, p - 1)
		x = max(x, l)
		(p, q) = (x, y)
		ans += q - p + 1
print(ans)


def get(l, i):
	c = 0
	while i < len(l):
		if l[i] % 10 == 1:
			if c == 0:
				return i
			else:
				c -= 1
		else:
			c += 1
		i += 1
	return i

def ans(p):
	c = 0
	i = 0
	while i < len(p):
		c1 = p[i]
		i = get(p, i + 1)
		c2 = p[i]
		c += c2 // 10 - c1 // 10 + 1
		i += 1
	return c
(n, l, r) = map(int, input().split())
p = list(map(int, input().split()))
p.sort()
p1 = []
i = 0
while i < n - 1:
	c1 = max(l, p[i + 1] - p[i] + 1)
	c2 = min(r, p[i + 1] + p[i] - 1)
	if c2 >= c1:
		p1 += [10 * c2 + 1, 10 * c1]
	i += 1
p1.sort()
print(ans(p1))


(n, l, r) = map(int, input().strip().split())
arr = [int(i) for i in input().strip().split()]
arr.sort(reverse=True)
ans = 0
for y in range(n):
	if y == n - 1:
		break
	x = arr[y + 1]
	i = arr[y]
	max = i + x - 1
	min = i - x + 1
	if max < r:
		r = max
	if min <= l:
		ans += r - l + 1
		break
	if min > r:
		continue
	ans += r - min + 1
	r = min - 1
	if r < l:
		break
print(ans)


from operator import itemgetter

def solve(a, l, r):
	ans = 0
	interval = []
	for i in range(n - 1, 0, -1):
		(x, y) = (a[i] - a[i - 1] + 1, a[i] + a[i - 1] - 1)
		interval.append([x, y])
	interval.sort(key=itemgetter(0, 1))
	for (x, y) in interval:
		x = max(x, l)
		y = min(y, r)
		if y < x:
			continue
		ans += y - x + 1
		l = y + 1
		if l > r:
			break
	return ans
(n, l, r) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
print(solve(a, l, r))


import sys
(n, l, r) = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
arr.sort(reverse=True)
(last, res) = (-1, 0)
for i in range(len(arr) - 1):
	a = max(l, arr[i] - arr[i + 1] + 1)
	b = min(r, arr[i] + arr[i + 1] - 1)
	if a > b:
		continue
	if last == -1 or b < last:
		res += b - a + 1
		last = a
	elif last > a:
		res += last - a
		last = a
print(res)


s = [int(i) for i in input().strip().split()]
(n, l, r) = (s[0], s[1], s[2])
arr = [int(i) for i in input().strip().split()]
arr.sort(reverse=True)
ct = 0
for i in range(n - 1):
	lo = arr[i] - arr[i + 1] + 1
	hi = arr[i] + arr[i + 1] - 1
	t1 = min(r, hi)
	t2 = max(l, lo)
	if t2 > t1:
		continue
	if t1 < l:
		break
	ct += t1 - t2 + 1
	r = t2 - 1
	if r < l:
		break
print(ct)


import heapq as pq
(n, L, R) = map(int, input().split())
ar = list(map(int, input().split()))
ar.sort()
vec = []
for i in range(1, n):
	vec.append((max(L - 1, ar[i] - ar[i - 1]), min(R + 1, ar[i] + ar[i - 1])))
pq.heapify(vec)
vec = [pq.heappop(vec) for i in range(n - 1)]
ans = 0
i = 0
while i < n - 1:
	st = vec[i][0]
	en = vec[i][1]
	i += 1
	while i < n - 1 and vec[i][0] < en:
		en = max(en, vec[i][1])
		i += 1
	if st < en:
		ans += en - st - 1
print(ans)


from random import randint
(n, l, r) = map(int, input().split())
a = list(map(int, input().split()))
b = []
a.sort()
for i in range(1, n):
	x = a[i - 1]
	y = a[i]
	if min(y + x - 1, r) - max(y - x + 1, l) + 1 <= 0:
		continue
	b.append([max(y - x + 1, l), min(y + x - 1, r)])
b.sort(key=lambda x: x[0])
ans = b[0][1] - b[0][0] + 1
ln = len(b)
r1 = b[0][1]
for i in range(1, ln):
	l2 = b[i][0]
	r2 = b[i][1]
	if r1 >= r2:
		continue
	ans += r2 - l2 + 1
	if l2 <= r1:
		ans -= r1 - l2 + 1
	r1 = r2
print(ans)


(n, l, r) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
t = [[a[1] - a[0] + 1, a[1] + a[0] - 1]]
for i in range(2, n):
	(x, y) = (a[i] - a[i - 1] + 1, a[i] + a[i - 1] - 1)
	while t and x <= t[-1][1]:
		(u, v) = t.pop()
		if x > u:
			x = u
	t.append([x, y])
c = 0
for i in t:
	(x, y) = (max(l, i[0]), min(r, i[1]))
	c += max(0, y - x + 1)
print(c)


(a, n, m) = map(int, input().split())
list1 = [int(i) for i in input().split()]
list1.sort()
ans = 0
for i in range(a - 1, 0, -1):
	(y, z) = (list1[i], list1[i - 1])
	(lo, hi) = (y - z + 1, y + z - 1)
	if m < lo or hi < n:
		continue
	if n >= lo and m <= hi:
		ans += m - n + 1
		break
	ans += min(hi, m) - max(lo, n) + 1
	m = max(lo, n) - 1
print(ans)


(a, b, c) = list(map(int, input().split()))
d = list(map(int, input().split()))
d.sort()
max = []
min = []
d.reverse()
for i in range(a - 1):
	max.append([d[i] + d[i + 1] - 1, d[i] - d[i + 1] + 1])
uppr = c
clwr = b
total = 0
for i in range(len(max)):
	if max[i][0] >= uppr:
		if max[i][1] >= clwr and max[i][1] <= uppr:
			total += uppr - max[i][1] + 1
			uppr = max[i][1] - 1
	if max[i][0] < uppr:
		if max[i][1] >= clwr:
			total += max[i][0] - max[i][1] + 1
			uppr = max[i][1] - 1
		if max[i][1] < clwr:
			total += max[i][0] - clwr + 1
			break
for i in range(1000):
	print('', end='')
print(total)


def intersection(L1, R1, L2, R2):
	(L3, R3) = (max(L1, L2), min(R1, R2))
	return (L3, R3) if L3 <= R3 else None
(N, L, R) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
L = [intersection(L, R, A[i] - A[i - 1] + 1, A[i] + A[i - 1] - 1) for i in range(1, N)]
L = [x for x in L if x is not None]
L.sort()
total = 0
pe = -1
for (s, e) in L:
	if s > pe:
		total += e - s + 1
		pe = e
	elif e > pe:
		total += e - pe
		pe = e
print(total)


import math
(n, l, r) = map(int, input().split())
ar = list(map(int, input().split()))
ar1 = []
ar.sort()
for i in range(n - 1, 0, -1):
	b = ar[i] + ar[i - 1]
	a = abs(ar[i] - ar[i - 1])
	ar1.append((a, b))
ar1.sort()
ar2 = []
ar2.append((ar1[0][0], ar1[0][1]))
for i in range(1, n - 1):
	tmp1 = ar1[i][0]
	tmp2 = ar1[i][1]
	(m, n) = ar2.pop()
	if n <= tmp1:
		ar2.append((m, n))
		ar2.append((tmp1, tmp2))
		continue
	elif n >= tmp2:
		ar2.append((m, n))
		continue
	elif n < tmp2:
		ar2.append((m, tmp2))
		continue
cnt = 0
for (a, b) in ar2:
	if a <= l and b >= r:
		if a == l:
			l += 1
		if b == r:
			r -= 1
		cnt += abs(l - r) + 1
	elif a > l and b >= r and (a < r):
		if b == r:
			cnt += abs(b - a) - 1
		else:
			cnt += abs(r - a)
	elif a <= l and b < r and (l < b):
		if a == l:
			cnt += abs(b - a) - 1
		else:
			cnt += abs(b - l)
	elif l < a and r > b:
		cnt += abs(abs(b - a)) - 1
print(cnt)