Given an array Arr[] of N distinct integers and a range from L to R, the task is to count the number of triplets having a sum in the range [L, R].
Example 1:
Input:
N = 4
Arr = {8 , 3, 5, 2}
L = 7, R = 11
Output: 1
Explaination: There is only one triplet {2, 3, 5}
having sum 10 in range [7, 11].
Example 2:
Input:
N = 5
Arr = {5, 1, 4, 3, 2}
L = 2, R = 7
Output: 2
Explaination: There two triplets having 
sum in range [2, 7] are {1,4,2} and {1,3,2}.
Your Task:
You don't need to read input or print anything. Your task is to complete the function countTriplets() which takes the array Arr[] and its size N and L and R as input parameters and returns the count.
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{3}
1 ≤ Arr[i] ≤ 10^{3}
1 ≤ L ≤ R ≤ 10^{9}

Difficulty: MEDIUM
Tags: Sorting
Skill types: Sorting
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

class Solution:
    def countTriplets(self, Arr, N, L, R):
        # code here

Solutions:
class Solution:

	def countTriplets(self, Arr, N, L, R):
		Arr.sort()
		n = len(Arr)
		a = 0
		b = 0
		for i in range(n - 2):
			j = i + 1
			k = n - 1
			while j < k:
				if Arr[i] + Arr[j] + Arr[k] <= R:
					a += k - j
					j += 1
				else:
					k -= 1
		for i in range(n - 2):
			j = i + 1
			k = n - 1
			while j < k:
				if Arr[i] + Arr[j] + Arr[k] <= L - 1:
					b += k - j
					j += 1
				else:
					k -= 1
		return a - b


class Solution:

	def countTriplets(self, Arr, N, L, R):
		if N < 3:
			return 0
		Arr.sort()
		res1 = 0
		for i in range(N - 2):
			(s, e) = (i + 1, N - 1)
			while s < e:
				sm = Arr[i] + Arr[s] + Arr[e]
				if sm <= R:
					res1 += e - s
					s += 1
				else:
					e -= 1
		res2 = 0
		for i in range(N - 2):
			(s, e) = (i + 1, N - 1)
			while s < e:
				sm = Arr[i] + Arr[s] + Arr[e]
				if sm <= L - 1:
					res2 += e - s
					s += 1
				else:
					e -= 1
		return abs(res1 - res2)


class Solution:

	def countTriplets(self, Arr, N, L, R):
		Arr.sort()
		count1 = 0
		count2 = 0
		for i in range(N):
			left = i + 1
			right = N - 1
			while left < right:
				if Arr[i] + Arr[right] + Arr[left] <= R:
					count1 += right - left
					left += 1
				else:
					right -= 1
		for i in range(N):
			left = i + 1
			right = N - 1
			while left < right:
				if Arr[i] + Arr[left] + Arr[right] <= L - 1:
					count2 += right - left
					left += 1
				else:
					right -= 1
		return abs(count1 - count2)


class Solution:

	def countTriplets(self, Arr, N, L, R):
		Arr.sort()
		ans = 0
		for i in range(N):
			j = i + 1
			k = N - 1
			while j < k:
				if Arr[i] + Arr[j] + Arr[k] <= R:
					ans += k - j
					j += 1
				elif Arr[i] + Arr[j] + Arr[k] > R:
					k -= 1
		ans2 = 0
		for i in range(N):
			j = i + 1
			k = N - 1
			while j < k:
				if Arr[i] + Arr[j] + Arr[k] <= L - 1:
					ans2 += k - j
					j += 1
				elif Arr[i] + Arr[j] + Arr[k] > L - 1:
					k -= 1
		return ans - ans2


class Solution:

	def count(self, Arr, N, val):
		Arr.sort()
		ans = 0
		j = 0
		k = 0
		sum = 0
		for i in range(0, N - 2):
			j = i + 1
			k = N - 1
			while j != k:
				sum = Arr[i] + Arr[j] + Arr[k]
				if sum > val:
					k -= 1
				else:
					ans += k - j
					j += 1
		return ans

	def countTriplets(self, Arr, N, L, R):
		return self.count(Arr, N, R) - self.count(Arr, N, L - 1)


class Solution:

	def smaller(self, arr, n, l, r):
		ans = 0
		for i in range(n - 1):
			j = i + 1
			k = n - 1
			while j < k:
				total = arr[i] + arr[j] + arr[k]
				if total < l:
					ans += k - j
					j += 1
				if total >= l:
					k -= 1
		return ans

	def greater(self, arr, n, l, r):
		ans = 0
		for i in range(n - 1):
			j = i + 1
			k = n - 1
			while j < k:
				total = arr[i] + arr[j] + arr[k]
				if total > r:
					ans += k - j
					k -= 1
				if total <= r:
					j += 1
		return ans

	def countTriplets(self, arr, n, l, r):
		arr.sort()
		c1 = self.smaller(arr, n, l, r)
		c2 = self.greater(arr, n, l, r)
		total = n * (n - 1) * (n - 2) // 6
		return total - (c1 + c2)


def countTripletsLessThan(arr, n, val):
	arr.sort()
	ans = 0
	j = 0
	k = 0
	sum = 0
	for i in range(0, n - 2):
		j = i + 1
		k = n - 1
		while j != k:
			sum = arr[i] + arr[j] + arr[k]
			if sum > val:
				k -= 1
			else:
				ans += k - j
				j += 1
	return ans

class Solution:

	def countTriplets(self, arr, n, a, b):
		res = 0
		res = countTripletsLessThan(arr, n, b) - countTripletsLessThan(arr, n, a - 1)
		return res


class Solution:

	def countTriplets(self, a, n, L, R):
		if n < 3:
			return 0
		a = sorted(a)
		c1 = 0
		for curr in range(n - 2):
			l = curr + 1
			r = n - 1
			while l < r:
				val = a[curr] + a[l] + a[r]
				if val > R:
					r -= 1
				else:
					c1 = c1 + r - l
					l += 1
		c2 = 0
		for curr in range(n - 2):
			l = curr + 1
			r = n - 1
			while l < r:
				val = a[curr] + a[l] + a[r]
				if val >= L:
					r -= 1
				else:
					c2 = c2 + r - l
					l += 1
		return c1 - c2


class Solution:

	def countTriplets(self, Arr, N, L, R):
		count = 0
		Arr.sort()
		for ele in range(N):
			i = ele + 1
			j = N - 1
			while i < j:
				a = Arr[ele] + Arr[i] + Arr[j]
				if a >= L and a <= R:
					e = i
					d = Arr[ele] + Arr[i]
					while Arr[i + 1] < L - d:
						i += 1
					count += j - i
					i = e + 1
				elif a > R:
					j -= 1
				elif a < L:
					i += 1
		return count


class Solution:

	def countTriplets(self, A, N, L, R):
		A.sort()
		count1 = 0
		K = R
		for i in range(N - 2):
			j = i + 1
			n = j
			k = N - 1
			while j < k:
				if A[i] + A[j] + A[k] <= K:
					count1 += k - j
					j += 1
				elif A[i] + A[j] + A[k] > K:
					k -= 1
		count2 = 0
		K = L - 1
		for i in range(N - 2):
			j = i + 1
			k = N - 1
			while j < k:
				if A[i] + A[j] + A[k] <= K:
					count2 += k - j
					j += 1
				elif A[i] + A[j] + A[k] > K:
					k -= 1
		return count1 - count2


def findTriplets(arr, n, sum):
	arr.sort()
	ans = 0
	for i in range(0, n - 1):
		l = i + 1
		r = n - 1
		x = arr[i]
		while l < r:
			if x + arr[l] + arr[r] <= sum:
				ans += r - l
				l += 1
			else:
				r = r - 1
	return ans

class Solution:

	def countTriplets(self, arr, N, L, R):
		return findTriplets(arr, N, R) - findTriplets(arr, N, L - 1)


class Solution:

	def countlesseq(self, arr, n, target):
		count = 0
		for i in range(n - 1):
			l = i + 1
			r = n - 1
			while l < r:
				total = arr[i] + arr[l] + arr[r]
				if total <= target:
					count = count + (r - l)
					l = l + 1
				else:
					r = r - 1
		return count

	def countTriplets(self, Arr, N, L, R):
		Arr.sort()
		return self.countlesseq(Arr, N, R) - self.countlesseq(Arr, N, L - 1)


class Solution:

	def countTriplets(self, Arr, N, L, R):
		Arr.sort()
		counti1 = 0
		counti2 = 0
		for i in range(N):
			j = i + 1
			k = N - 1
			while j < k:
				if Arr[i] + Arr[j] + Arr[k] <= R:
					counti1 += k - j
					j += 1
				else:
					k -= 1
		for i in range(N):
			j = i + 1
			k = N - 1
			while j < k:
				if Arr[i] + Arr[j] + Arr[k] < L:
					counti2 += k - j
					j += 1
				else:
					k -= 1
		return counti1 - counti2


class Solution:

	def countTriplets(self, Arr, N, L, R):
		Arr.sort()
		count1 = 0
		count2 = 0
		triplets = 0
		i = 0
		while i < N - 2:
			low = i + 1
			high = N - 1
			while low < high:
				if Arr[i] + Arr[low] + Arr[high] <= R:
					count1 += high - low
					low += 1
				else:
					high -= 1
			i += 1
		i = 0
		while i < N - 2:
			low = i + 1
			high = N - 1
			while low < high:
				if Arr[i] + Arr[low] + Arr[high] <= L - 1:
					count2 += high - low
					low += 1
				else:
					high -= 1
			i += 1
		triplets = count1 - count2
		return abs(triplets)


class Solution:

	def countvalues(self, arr, n, value):
		arr.sort()
		j = 0
		k = 0
		summ = 0
		ans = 0
		for i in range(0, n - 2):
			j = i + 1
			k = n - 1
			while j != k:
				summ = arr[i] + arr[j] + arr[k]
				if summ > value:
					k = k - 1
				else:
					ans = ans + k - j
					j = j + 1
		return ans

	def countTriplets(self, Arr, N, L, R):
		result = 0
		result1 = self.countvalues(Arr, N, R)
		result2 = self.countvalues(Arr, N, L - 1)
		result = result1 - result2
		return result


class Solution:

	def countTriplets(self, A, N, L, R):
		if N < 3:
			return 0

		def twopointer(A, N, tar):
			ans = 0
			for i in range(N - 2):
				j = i + 1
				k = N - 1
				while k > j:
					sm = A[i] + A[j] + A[k]
					if sm <= tar:
						ans += k - j
						j += 1
					else:
						k -= 1
			return ans
		A.sort()
		return twopointer(A, N, R) - twopointer(A, N, L - 1)


class Solution:

	def count_the_triplet(self, Arr, N, X):
		count = 0
		Arr.sort()
		for i in range(N - 2):
			j = i + 1
			k = N - 1
			while j < k:
				if Arr[i] + Arr[j] + Arr[k] <= X:
					count += k - j
					j += 1
				else:
					k -= 1
		return count

	def countTriplets(self, Arr, N, L, R):
		return self.count_the_triplet(Arr, N, R) - self.count_the_triplet(Arr, N, L - 1)


class Solution:

	def countTriplets(self, Arr, N, L, R):

		def findpair(arr, target):
			start = 0
			nonlocal count
			end = len(arr) - 1
			while start < end:
				if arr[start] + arr[end] <= target:
					count += end - start
					start += 1
				else:
					end -= 1

		def findpairlarger(arr, target):
			start = 0
			nonlocal countl
			end = len(arr) - 1
			while start < end:
				if arr[start] + arr[end] < target:
					countl += end - start
					start += 1
				else:
					end -= 1
		Arr.sort()
		count = 0
		countl = 0
		for i in range(len(Arr) - 1):
			s = findpair(Arr[i + 1:], R - Arr[i])
			t = findpairlarger(Arr[i + 1:], L - Arr[i])
		return count - countl


class Solution:

	def countTriplets(self, Arr, N, L, R):
		Arr.sort()
		lower = 0
		upper = 0
		for i in range(len(Arr)):
			start = i + 1
			end = len(Arr) - 1
			while start < end:
				summ = Arr[start] + Arr[end]
				if summ < L - Arr[i]:
					lower += end - start
					start += 1
				else:
					end -= 1
		for i in range(len(Arr)):
			start = i + 1
			end = len(Arr) - 1
			while start < end:
				summ = Arr[start] + Arr[end]
				if summ <= R - Arr[i]:
					upper += end - start
					start += 1
				else:
					end -= 1
		return upper - lower


class Solution:

	def countTriplets(self, Arr, N, L, R):
		Arr.sort()
		cnt1 = 0
		cnt2 = 0
		for i in range(N - 2):
			l = i + 1
			r = N - 1
			while l < r:
				if Arr[i] + Arr[l] + Arr[r] <= L - 1:
					cnt1 += r - l
					l += 1
				else:
					r -= 1
		for i in range(N - 2):
			l = i + 1
			r = N - 1
			while l < r:
				if Arr[i] + Arr[l] + Arr[r] <= R:
					cnt2 += r - l
					l += 1
				else:
					r -= 1
		return abs(cnt2 - cnt1)


class Solution:

	def countTriplets(self, arr, n, a, b):
		arr.sort()
		cnt1 = 0
		cnt2 = 0
		for i in range(n - 2):
			x1 = 0
			left1 = i + 1
			right1 = n - 1
			while left1 < right1:
				if arr[left1] + arr[i] + arr[right1] < a:
					x1 += right1 - left1
					left1 += 1
				else:
					right1 -= 1
			cnt1 += x1
		for i in range(n - 2):
			x2 = 0
			(left2, right2) = (i + 1, n - 1)
			while left2 < right2:
				if arr[left2] + arr[i] + arr[right2] < b + 1:
					x2 += right2 - left2
					left2 += 1
				else:
					right2 -= 1
			cnt2 += x2
		return cnt2 - cnt1


class Solution:

	def countTriplets(self, arr, N, L, R):

		def countPairs(arr, firstValue, start, target):
			left = start
			count = 0
			right = len(arr) - 1
			while left < right:
				if firstValue + arr[left] + arr[right] <= target:
					count += right - left
					left += 1
				else:
					right -= 1
			return count
		arr.sort()
		countL = 0
		countR = 0
		count = 0
		for i in range(len(arr)):
			countL += countPairs(arr, arr[i], i + 1, L - 1)
			countR += countPairs(arr, arr[i], i + 1, R)
		count += countR - countL
		return count


class Solution:

	def countTriplets(self, Arr, N, L, R):
		Arr = sorted(Arr)
		left_count = 0
		right_count = 0
		for i in range(N - 2):
			left_count += self.target_pair(Arr, i + 1, L - 1, N, Arr[i])
			right_count += self.target_pair(Arr, i + 1, R, N, Arr[i])
		ans = right_count - left_count
		return ans

	def target_pair(self, Arr, start, target, N, val):
		end = N - 1
		count = 0
		while start < end:
			if val + Arr[start] + Arr[end] <= target:
				count += end - start
				start += 1
			else:
				end -= 1
		return count


class Solution:

	def countTriplets(self, Arr, N, L, R):
		Arr.sort()
		c = 0
		c1 = 0
		for i in range(len(Arr) - 2):
			j = i + 1
			k = N - 1
			while j < k:
				s = Arr[i] + Arr[j] + Arr[k]
				if s < L:
					c += k - j
					j += 1
				elif s >= L:
					k -= 1
		for i in range(len(Arr) - 2):
			j = i + 1
			k = N - 1
			while j < k:
				s = Arr[i] + Arr[j] + Arr[k]
				if s <= R:
					c1 += k - j
					j += 1
				elif s > L:
					k -= 1
		return c1 - c


class Solution:

	def countTriplets(self, Arr, N, L, R):

		def findPairCount(arr, curr, start, range):
			end = len(arr) - 1
			count = 0
			while start < end:
				if arr[curr] + arr[start] + arr[end] < range:
					count += end - start
					start += 1
				elif arr[curr] + arr[start] + arr[end] >= range:
					end -= 1
			return count
		Arr.sort()
		lowerCount = 0
		higherCount = 0
		for i in range(N - 2):
			if i > 0 and Arr[i] == Arr[i - 1]:
				continue
			lowerCount += findPairCount(Arr, i, i + 1, L)
			higherCount += findPairCount(Arr, i, i + 1, R + 1)
		return higherCount - lowerCount


class Solution:

	def countTriplets(self, arr, n, L, R):

		def rpair(first, target, start, end, arr):
			count = 0
			while start < end:
				sm = first + arr[start] + arr[end]
				if sm <= target:
					count += end - start
					start += 1
				else:
					end -= 1
			return count

		def lpair(first, target, start, end, arr):
			count = 0
			while start < end:
				sm = first + arr[start] + arr[end]
				if sm < target:
					count += end - start
					start += 1
				else:
					end -= 1
			return count
		arr = sorted(arr)
		(lcount, rcount) = (0, 0)
		for i in range(n - 2):
			rcount += rpair(arr[i], R, i + 1, n - 1, arr)
			lcount += lpair(arr[i], L, i + 1, n - 1, arr)
		return rcount - lcount


class Solution:

	def countTriplets(self, num, N, L, R):
		num.sort()
		c = 0
		c1 = 0
		for i in range(len(num) - 2):
			(l, r) = (i + 1, len(num) - 1)
			while l < r:
				Sum = num[i] + num[l] + num[r]
				if Sum < L:
					c += r - l
					l += 1
				elif Sum >= L:
					r -= 1
		for i in range(len(num) - 2):
			(l, r) = (i + 1, len(num) - 1)
			while l < r:
				Sum = num[i] + num[l] + num[r]
				if Sum <= R:
					c1 += r - l
					l += 1
				elif Sum > R:
					r -= 1
		return c1 - c


class Solution:

	def countTriplets(self, Arr, N, L, R):
		Arr.sort()
		count1 = 0
		for i in range(N - 2):
			l = i + 1
			r = N - 1
			while l < r:
				suma = Arr[i] + Arr[l] + Arr[r]
				if suma < L:
					count1 += r - l
					l += 1
				else:
					r -= 1
		count2 = 0
		for i in range(N - 2):
			l = i + 1
			r = N - 1
			while l < r:
				suma = Arr[i] + Arr[l] + Arr[r]
				if suma > R:
					count2 += r - l
					r -= 1
				else:
					l += 1
		total = int(N * (N - 1) * (N - 2) / 6)
		return total - count1 - count2


class Solution:

	def countTriplets(self, Arr, N, L, R):
		Arr.sort()
		c = 0
		for i in range(N - 2):
			j = i + 1
			k = N - 1
			while j < k:
				g = Arr[i] + Arr[j] + Arr[k]
				if g >= L and g <= R:
					h = j + 1
					while h < k and Arr[i] + Arr[j] + Arr[h] < L:
						h += 1
					c += k - h + 1
					j += 1
				elif g > R:
					k -= 1
				else:
					j += 1
		return c


class Solution:

	def sum_less_than_equal(self, A, N, target):
		A.sort()
		count = 0
		i = 0
		while i < N:
			j = i + 1
			k = len(A) - 1
			while j < k:
				summ = A[i] + A[j] + A[k]
				if summ > target:
					k -= 1
				else:
					count += k - j
					j += 1
			i += 1
		return count

	def countTriplets(self, A, N, L, R):
		return self.sum_less_than_equal(A, N, R) - self.sum_less_than_equal(A, N, L - 1)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		Arr = input().split()
		for itr in range(N):
			Arr[itr] = int(Arr[itr])
		(L, R) = input().split()
		L = int(L)
		R = int(R)
		ob = Solution()
		print(ob.countTriplets(Arr, N, L, R))


class Solution:

	def countLessOrEqual(self, arr, n, k):
		c = 0
		for i in range(n - 1):
			(l, r) = (i + 1, n - 1)
			while l < r:
				sum = arr[i] + arr[l] + arr[r]
				if sum <= k:
					c += r - l
					l += 1
				else:
					r -= 1
		return c

	def countTriplets(self, arr, N, L, R):
		arr.sort()
		return self.countLessOrEqual(arr, N, R) - self.countLessOrEqual(arr, N, L - 1)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		Arr = input().split()
		for itr in range(N):
			Arr[itr] = int(Arr[itr])
		(L, R) = input().split()
		L = int(L)
		R = int(R)
		ob = Solution()
		print(ob.countTriplets(Arr, N, L, R))


class Solution:

	def countTriplets(self, arr, N, L, R):
		cnt = 0
		arr.sort()

		def solve(val):
			cnt = 0
			for k in range(N - 1, -1, -1):
				i = 0
				j = k - 1
				while i < j:
					s = arr[i] + arr[j] + arr[k]
					if s >= val:
						cnt += j - i
						j -= 1
					else:
						i += 1
			return cnt
		cnt1 = solve(R + 1)
		cnt2 = solve(L)
		return cnt2 - cnt1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		Arr = input().split()
		for itr in range(N):
			Arr[itr] = int(Arr[itr])
		(L, R) = input().split()
		L = int(L)
		R = int(R)
		ob = Solution()
		print(ob.countTriplets(Arr, N, L, R))


class Solution:

	def countTripletsLessThan(self, Arr, N, val):
		ans = 0
		j = 0
		k = 0
		trip_sum = 0
		for i in range(0, N - 2):
			j = i + 1
			k = N - 1
			while j != k:
				trip_sum = Arr[i] + Arr[j] + Arr[k]
				if trip_sum > val:
					k -= 1
				else:
					ans += k - j
					j += 1
		return ans

	def countTriplets(self, Arr, N, L, R):
		res = 0
		Arr.sort()
		res = self.countTripletsLessThan(Arr, N, R) - self.countTripletsLessThan(Arr, N, L - 1)
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		Arr = input().split()
		for itr in range(N):
			Arr[itr] = int(Arr[itr])
		(L, R) = input().split()
		L = int(L)
		R = int(R)
		ob = Solution()
		print(ob.countTriplets(Arr, N, L, R))


class Solution:

	def countTriplets(self, a, n, l, r):
		return rt(a, n, l, r)

def rt(a, n, l, r):
	c = 0
	c1 = 0
	a.sort()
	l = l - 1
	for i in range(0, len(a) - 2):
		l1 = i + 1
		h1 = len(a) - 1
		while l1 < h1:
			if a[i] + a[l1] + a[h1] <= l:
				c = c + h1 - l1
				l1 += 1
			else:
				h1 -= 1
	for i in range(0, len(a) - 2):
		l1 = i + 1
		h1 = len(a) - 1
		while l1 < h1:
			if a[i] + a[l1] + a[h1] <= r:
				c1 = c1 + h1 - l1
				l1 += 1
			else:
				h1 -= 1
	return c1 - c


class Solution:

	def countTriplets(self, Arr, N, L, R):
		res = self.countTripletsLessThan(Arr, R) - self.countTripletsLessThan(Arr, L - 1)
		return res

	def countTripletsLessThan(self, Arr, val):
		count = 0
		Arr.sort()
		for i in range(len(Arr) - 2):
			j = i + 1
			k = len(Arr) - 1
			while j < k:
				total = Arr[i] + Arr[j] + Arr[k]
				if total > val:
					k -= 1
				else:
					count += k - j
					j += 1
		return count


class Solution:

	def helper(self, arr, N, K):
		res = 0
		for i in range(N - 1):
			j = i + 1
			k = N - 1
			while j < k:
				if arr[i] + arr[j] + arr[k] > K:
					k -= 1
				else:
					res += k - j
					j += 1
		return res

	def countTriplets(self, arr, N, L, R):
		arr.sort()
		c1 = self.helper(arr, N, L - 1)
		c2 = self.helper(arr, N, R)
		return c2 - c1


class Solution:

	def countTriplets(self, arr, n, L, R):
		arr = sorted(arr)
		greater = self.countsum(arr, R, True)
		smaller = self.countsum(arr, L, False)
		return greater - smaller

	def countsum(self, arr, val, equal):
		k = len(arr) - 1
		count = 0
		while k >= 2:
			i = 0
			j = k - 1
			while j > i:
				currsum = arr[i] + arr[j] + arr[k]
				if equal and currsum == val:
					count += j - i
					i += 1
				elif currsum < val:
					count += j - i
					i += 1
				else:
					j -= 1
			k -= 1
		return count


class Solution:

	def countTriplets(self, Arr, N, L, R):
		if N < 3:
			return 0
		Arr.sort()
		sum = 0
		count = 0
		for i in range(2, N):
			sp1 = 0
			ep1 = i - 1
			sp2 = 0
			ep2 = i - 1
			while sp1 < ep1:
				sum_ = Arr[sp1] + Arr[ep1] + Arr[i]
				if sum_ < L:
					sum += ep1 - sp1
					sp1 += 1
				else:
					ep1 -= 1
			while sp2 < ep2:
				sum_ = Arr[sp2] + Arr[ep2] + Arr[i]
				if sum_ > R:
					sum += ep2 - sp2
					ep2 -= 1
				else:
					sp2 += 1
		total = N * (N - 1) * (N - 2) // 6
		return total - sum


class Solution:

	def countTriplets(self, arr, n, L, R):
		count1 = 0
		arr.sort()
		for i in range(len(arr)):
			j = i + 1
			k = n - 1
			while j < k:
				if arr[i] + arr[j] + arr[k] < L:
					count1 += k - j
					j += 1
				else:
					k -= 1
		count2 = 0
		for i in range(len(arr)):
			j = i + 1
			k = n - 1
			while j < k:
				if arr[i] + arr[j] + arr[k] <= R:
					count2 += k - j
					j += 1
				else:
					k -= 1
		return abs(count2 - count1)


class Solution:

	def countTriplets(self, arr, N, a, b):

		def sol(nums, X):
			res = []
			nums.sort()
			ans = 0
			for (i, a) in enumerate(nums):
				(l, r) = (i + 1, len(nums) - 1)
				while l < r:
					threeSum = a + nums[l] + nums[r]
					if threeSum > X:
						r -= 1
					else:
						ans += r - l
						l += 1
			return ans
		res = 0
		res = sol(arr, b) - sol(arr, a - 1)
		return res


class Solution:

	def countTriplets(self, Arr, N, L, R):
		if N < 3:
			return 0
		Arr.sort()
		less_than_R = 0
		for i in range(0, N - 2):
			j = i + 1
			k = N - 1
			while j < k:
				sum = Arr[i] + Arr[j] + Arr[k]
				if sum <= R:
					less_than_R += k - j
					j += 1
				else:
					k -= 1
		less_than_L = 0
		for i in range(0, N - 2):
			j = i + 1
			k = N - 1
			while j < k:
				sum = Arr[i] + Arr[j] + Arr[k]
				if sum <= L - 1:
					less_than_L += k - j
					j += 1
				else:
					k -= 1
		return abs(less_than_L - less_than_R)


class Solution:

	def countTriplets(self, Arr, N, L, R):
		Arr.sort()
		count1 = 0
		count2 = 0
		total = int(N * (N - 1) * (N - 2) / 6)
		for i in range(N - 2):
			low = i + 1
			high = N - 1
			while low < high:
				sums = Arr[i] + Arr[low] + Arr[high]
				if sums < L:
					count1 += high - low
					low += 1
				else:
					high -= 1
		for i in range(N - 2):
			low = i + 1
			high = N - 1
			while low < high:
				sums = Arr[i] + Arr[low] + Arr[high]
				if sums > R:
					count2 += high - low
					high -= 1
				else:
					low += 1
		return total - (count1 + count2)


def findCount(nums, target):
	count = 0
	for i in range(len(nums)):
		(low, high) = (i + 1, len(nums) - 1)
		while low < high:
			if nums[i] + nums[high] + nums[low] > target:
				high -= 1
			else:
				count += high - low
				low += 1
	return count

class Solution:

	def countTriplets(self, Arr, N, L, R):
		Arr.sort()
		res = findCount(Arr, R) - findCount(Arr, L - 1)
		return res


class Solution:

	def fn(self, a, val, n):
		ans = 0
		for k in range(n - 2):
			i = k + 1
			j = n - 1
			while i < j:
				su = a[i] + a[j] + a[k]
				if su > val:
					j -= 1
				else:
					ans += j - i
					i += 1
		return ans

	def countTriplets(self, a, n, l, r):
		a.sort()
		return self.fn(a, r, n) - self.fn(a, l - 1, n)


class Solution:

	def countTriplets(self, Arr, N, L, R):
		Arr.sort()
		(cnt1, cnt2) = (0, 0)
		for i in range(N - 2):
			low = i + 1
			high = N - 1
			while low < high:
				Sum = Arr[i] + Arr[low] + Arr[high]
				if Sum <= L - 1:
					cnt1 += high - low
					low += 1
				else:
					high -= 1
		for i in range(N - 2):
			low = i + 1
			high = N - 1
			while low < high:
				Sum = Arr[i] + Arr[low] + Arr[high]
				if Sum > R:
					high -= 1
				else:
					cnt2 += high - low
					low += 1
		return cnt2 - cnt1


class Solution:

	def countTriplets(self, Arr, N, L, R):
		Arr.sort()
		(tripletsR, tripletsL) = (0, 0)
		for i in range(N - 2):
			start = i + 1
			end = N - 1
			while start < end:
				totalSum = Arr[i] + Arr[start] + Arr[end]
				if totalSum <= R:
					tripletsR += end - start
					start += 1
				else:
					end -= 1
		for i in range(N - 2):
			start = i + 1
			end = N - 1
			while start < end:
				totalSum = Arr[i] + Arr[start] + Arr[end]
				if totalSum <= L - 1:
					tripletsL += end - start
					start += 1
				else:
					end -= 1
		return tripletsR - tripletsL


class Solution:

	def triplets_lessthanK(self, arr, n, val):
		ans = 0
		for x in range(n - 2):
			l = x + 1
			r = n - 1
			while l < r:
				if arr[x] + arr[l] + arr[r] >= val:
					r -= 1
				else:
					ans += r - l
					l += 1
		return ans

	def countTriplets(self, arr, N, L, R):
		arr.sort()
		out = self.triplets_lessthanK(arr, N, R + 1) - self.triplets_lessthanK(arr, N, L)
		return out


class Solution:

	def countTriplets(self, arr, N, L, R):
		lower = self.getTripletsCount(arr, N, L - 1)
		upper = self.getTripletsCount(arr, N, R)
		return upper - lower

	def getTripletsCount(self, arr, N, target):
		count = 0
		arr.sort()
		for i in range(N - 2):
			j = i + 1
			k = N - 1
			while j < k:
				total = arr[i] + arr[j] + arr[k]
				if total <= target:
					count += k - j
					j += 1
				else:
					k -= 1
		return count


class Solution:

	def triplets_lessthanK(self, arr, n, val):
		ans = 0
		sum = 0
		for i in range(0, n - 2):
			j = i + 1
			k = n - 1
			while j != k:
				sum = arr[i] + arr[j] + arr[k]
				if sum >= val:
					k -= 1
				else:
					ans += k - j
					j += 1
		return ans

	def countTriplets(self, arr, N, L, R):
		arr.sort()
		out = self.triplets_lessthanK(arr, N, R + 1) - self.triplets_lessthanK(arr, N, L)
		return out


class Solution:

	def countTriplets(self, arr, N, L, R):
		arr.sort()
		ans = 0
		s = 0
		lt = []
		for i in range(N - 1, 0, -1):
			k = 0
			j = i - 1
			while k < j:
				t = arr[i] + arr[k] + arr[j]
				if t >= L:
					ans += j - k
					j -= 1
				else:
					k += 1
		ans1 = 0
		for i in range(N - 1, 0, -1):
			k = 0
			j = i - 1
			while k < j:
				t = arr[i] + arr[k] + arr[j]
				if t > R:
					ans1 += j - k
					j -= 1
				else:
					k += 1
		return ans - ans1


class Solution:

	def countTriplets(self, Arr, N, L, R):

		def counter(arr, n, var):
			ans = 0
			for i in range(0, n - 2):
				j = i + 1
				k = n - 1
				while j != k:
					sum = arr[i] + arr[j] + arr[k]
					if sum > var:
						k -= 1
					else:
						ans += k - j
						j += 1
			return ans
		res = 0
		Arr.sort()
		res = counter(Arr, N, R) - counter(Arr, N, L - 1)
		return res


class Solution:

	def numTripletsLessThan(self, arr, val, N):
		cnt = 0
		for i in range(N):
			j = i + 1
			k = N - 1
			while j < k:
				if arr[i] + arr[j] + arr[k] >= val:
					k -= 1
				else:
					cnt += k - j
					j += 1
		return cnt

	def countTriplets(self, Arr, N, L, R):
		arr = Arr
		arr.sort()
		y = self.numTripletsLessThan(arr, R + 1, N)
		x = self.numTripletsLessThan(arr, L, N)
		return y - x


class Solution:

	def triplets_less_than_range(self, arr, k):
		res = 0
		for i in range(len(arr) - 1, 1, -1):
			left = 0
			right = i - 1
			while left < right:
				if arr[left] + arr[right] + arr[i] > k:
					right -= 1
				else:
					res += right - left
					left += 1
		return res

	def countTriplets(self, Arr, N, L, R):
		Arr.sort()
		triplets = 0
		n1 = self.triplets_less_than_range(Arr, L - 1)
		n2 = self.triplets_less_than_range(Arr, R)
		return n2 - n1


class Solution:

	def countTriplets(self, Arr, N, L, R):
		Arr.sort()
		n = N
		count1 = 0
		for i in range(N):
			lower = L - Arr[i] - 1
			j = i + 1
			k = N - 1
			while j < k:
				rem = Arr[j] + Arr[k]
				if rem <= lower:
					count1 += k - j
					j += 1
				elif rem > lower:
					k = k - 1
		count2 = 0
		for i in range(N):
			upper = R - Arr[i]
			j = i + 1
			k = N - 1
			while j < k:
				rem = Arr[j] + Arr[k]
				if rem <= upper:
					count2 += k - j
					j += 1
				elif rem > upper:
					k = k - 1
		return count2 - count1


class Solution:

	def count(self, arr, n, K):
		ans = 0
		for i in range(n - 1, 1, -1):
			low = 0
			high = i - 1
			while low < high:
				if arr[low] + arr[high] + arr[i] > K:
					high -= 1
				else:
					ans += high - low
					low += 1
		return ans

	def countTriplets(self, arr, n, L, R):
		arr.sort()
		return self.count(arr, n, R) - self.count(arr, n, L - 1)


class Solution:

	def countTriplets(self, Arr, N, L, R):
		Arr.sort()
		result = self.find_count(Arr, N, R) - self.find_count(Arr, N, L - 1)
		return result

	def find_count(self, nums, n, target):
		count = 0
		for i in range(0, n - 2):
			low = i + 1
			high = n - 1
			while low < high:
				s = nums[i] + nums[low] + nums[high]
				if s > target:
					high -= 1
				else:
					count += high - low
					low += 1
		return count


class Solution:

	def solve(self, arr, target):
		count = 0
		n = len(arr)
		for i in range(n):
			j = i + 1
			k = n - 1
			while j < k:
				_sum = arr[i] + arr[j] + arr[k]
				if _sum <= target:
					count += k - j
					j += 1
				else:
					k -= 1
		return count

	def countTriplets(self, Arr, N, L, R):
		Arr.sort()
		x = self.solve(Arr, R)
		y = self.solve(Arr, L - 1)
		return x - y


class Solution:

	def countTriplets(self, Arr, N, L, R):
		Arr.sort()
		count = 0
		for i in range(N):
			j = i + 1
			k = N - 1
			while j < k:
				sum_ = Arr[i] + Arr[j] + Arr[k]
				if sum_ < L:
					count += k - j
					j += 1
				else:
					k -= 1
		for i in range(N):
			j = i + 1
			k = N - 1
			while j < k:
				sum_ = Arr[i] + Arr[j] + Arr[k]
				if sum_ > R:
					count += k - j
					k -= 1
				else:
					j += 1
		total = int(N * (N - 2) * (N - 1) / 6)
		return total - count


class Solution:

	def countTriplets(self, Arr, N, L, R):
		count = 0
		Arr.sort()
		total = N * (N - 1) * (N - 2) // 6
		count_1 = 0
		count_2 = 0
		for i in range(N - 1):
			l = i + 1
			r = N - 1
			while l < r:
				if Arr[i] + Arr[l] + Arr[r] < L:
					count_1 += r - l
					l += 1
				else:
					r -= 1
		for i in range(N - 1):
			l = i + 1
			r = N - 1
			while l < r:
				if Arr[i] + Arr[l] + Arr[r] > R:
					count_1 += r - l
					r -= 1
				else:
					l += 1
		return total - (count_1 + count_2)


class Solution:

	def countTriplets(self, Arr, N, L, R):
		if N < 3:
			return 0
		return self.countTripletsBoundary(Arr, N, R) - self.countTripletsBoundary(Arr, N, L - 1)

	def countTripletsBoundary(self, Arr, N, T):
		Arr.sort()
		vCount = 0
		vLoopSum = 0
		for i in range(0, N - 2, 1):
			low = i + 1
			high = N - 1
			while low < high:
				vLoopSum = Arr[i] + Arr[low] + Arr[high]
				if vLoopSum > T:
					high -= 1
				else:
					vCount += high - low
					low += 1
		return vCount


class Solution:

	def countTriplets(self, a, N, L, R):
		a = sorted(a)
		count = 0
		for i in range(N):
			j = i + 1
			k = N - 1
			while j < k:
				s = a[i] + a[j] + a[k]
				if s < L:
					count += k - j
					j += 1
				else:
					k -= 1
		count1 = 0
		for i in range(N):
			j = i + 1
			k = N - 1
			while j < k:
				s = a[i] + a[j] + a[k]
				if s > R:
					count1 += k - j
					k -= 1
				else:
					j += 1
		total = int(N * (N - 1) * (N - 2) / 6)
		return total - (count + count1)


class Solution:

	def countTriplets(self, arr, n, l, r):
		arr.sort()
		countLessL = 0
		countGreaterR = 0
		totalTriplets = n * (n - 1) * (n - 2) // 6
		for i in range(n - 2):
			start = i + 1
			end = n - 1
			target = l - arr[i]
			while start < end:
				s = arr[start] + arr[end]
				if s < target:
					countLessL += end - start
					start += 1
				else:
					end -= 1
		for i in range(n - 2):
			start = i + 1
			end = n - 1
			target = r - arr[i]
			while start < end:
				s = arr[start] + arr[end]
				if s > target:
					countGreaterR += end - start
					end -= 1
				else:
					start += 1
		return totalTriplets - countGreaterR - countLessL


class Solution:

	def countTriplets(self, arr, n, l, r):
		arr.sort()

		def countLesserEqual(x):
			count = 0
			for i in range(n - 2):
				start = i + 1
				end = n - 1
				target = x - arr[i]
				while start < end:
					s = arr[start] + arr[end]
					if s <= target:
						count += end - start
						start += 1
					else:
						end -= 1
			return count
		return countLesserEqual(r) - countLesserEqual(l - 1)


from itertools import combinations

class Solution:

	def trip(self, arr, n, t):
		ans = 0
		for i in range(0, n - 2):
			j = i + 1
			k = n - 1
			while j != k:
				sum = arr[i] + arr[j] + arr[k]
				if sum > t:
					k -= 1
				else:
					ans += k - j
					j += 1
		return ans

	def countTriplets(self, arr, N, L, R):
		arr.sort()
		count = self.trip(arr, N, R) - self.trip(arr, N, L - 1)
		return count


class Solution:

	def countTriplets(self, Arr, N, L, R):

		def helper(Arr, N, target):
			count = 0
			for i in range(0, N - 2):
				start = i + 1
				end = N - 1
				s = 0
				while start != end:
					s = Arr[i] + Arr[start] + Arr[end]
					if s > target:
						end -= 1
					else:
						count += end - start
						start += 1
			return count
		ans = 0
		Arr.sort()
		left = helper(Arr, N, L - 1)
		right = helper(Arr, N, R)
		ans = right - left
		return ans


class Solution:

	def countTriplets(self, Arr, N, L, R):
		Arr.sort()
		c1 = self.helper(Arr, N, L - 1)
		c2 = self.helper(Arr, N, R)
		return c2 - c1

	def helper(self, a, n, x):
		res = 0
		for i in range(0, n - 1):
			j = i + 1
			k = n - 1
			while j < k:
				sum = a[i] + a[j] + a[k]
				if sum > x:
					k -= 1
				else:
					res += k - j
					j += 1
		return res


class Solution:

	def count(self, a, N, K):
		ans = 0
		a.sort()
		for i in range(N - 1):
			j = i + 1
			k = N - 1
			while j < k:
				if a[i] + a[j] + a[k] > K:
					k -= 1
				else:
					ans += k - j
					j += 1
		return ans

	def countTriplets(self, a, N, L, R):
		ans = self.count(a, N, R) - self.count(a, N, L - 1)
		return ans


class Solution:

	def countTriplets(self, Arr, N, L, R):
		Arr.sort()
		count1 = 0
		for i in range(N - 2):
			l = i + 1
			r = N - 1
			while l < r:
				sum = Arr[i] + Arr[l] + Arr[r]
				if sum > R:
					r -= 1
				else:
					count1 += r - l
					l += 1
		count2 = 0
		for i in range(N - 2):
			l = i + 1
			r = N - 1
			while l < r:
				sum = Arr[i] + Arr[l] + Arr[r]
				if sum > L - 1:
					r -= 1
				else:
					count2 += r - l
					l += 1
		return count1 - count2


class Solution:

	def cnt_less_than(self, arr, n, maxi):
		cnt = j = k = 0
		for i in range(0, n - 2):
			j = i + 1
			k = n - 1
			while j != k:
				if arr[i] + arr[j] + arr[k] <= maxi:
					cnt += k - j
					j += 1
					continue
				k -= 1
		return cnt

	def countTriplets(self, arr, n, mini, maxi):
		arr.sort()
		ob = Solution()
		return ob.cnt_less_than(arr, n, maxi) - ob.cnt_less_than(arr, n, mini - 1)


class Solution:

	def solve(self, a, n, k):
		ans = 0
		for i in range(n):
			x = a[i]
			low = i + 1
			high = n - 1
			while low < high:
				s = x + a[low] + a[high]
				if s > k:
					high -= 1
				else:
					ans += high - low
					low += 1
		return ans

	def countTriplets(self, Arr, N, L, R):
		Arr.sort()
		return self.solve(Arr, N, R) - self.solve(Arr, N, L - 1)


class Solution:

	def countTriplets(self, Arr, N, L, R):
		Arr.sort()
		mins = self.minSum(Arr, N, L)
		Arr.sort(reverse=True)
		maxs = self.maxSum2(Arr, N, R)
		total = int(N * (N - 1) * (N - 2) / 6)
		return total - (mins + maxs)

	def minSum(self, arr, N, L):
		count = 0
		for i in range(N - 2):
			j = i + 1
			k = N - 1
			while j < k:
				sum = arr[i] + arr[j] + arr[k]
				if sum < L:
					count += k - j
					j = j + 1
				else:
					k = k - 1
		return count

	def maxSum(self, arr, N, R):
		count = 0
		for i in range(N - 2):
			j = i + 1
			k = j + 1
			while k < N:
				sum = arr[i] + arr[j] + arr[k]
				if sum > R:
					count += N - k
					j = j + 1
					k = j + 1
				else:
					k = k + 1
		return count

	def maxSum2(self, arr, N, R):
		count = 0
		for i in range(N - 2):
			j = i + 1
			k = N - 1
			while j < k:
				sum = arr[i] + arr[j] + arr[k]
				if sum > R:
					count += k - j
					j = j + 1
				else:
					k = k - 1
		return count


class Solution:

	def triplets_sum(self, ls, n, sum1):
		count = 0
		for i in range(n - 2):
			j = i + 1
			k = n - 1
			while j != k:
				d = ls[i] + ls[j] + ls[k]
				if d > sum1:
					k -= 1
				else:
					count += k - j
					j += 1
		return count

	def countTriplets(self, Arr, N, L, R):
		count = 0
		Arr.sort()
		count = self.triplets_sum(Arr, N, R) - self.triplets_sum(Arr, N, L - 1)
		return count