Given an array A[] of N integers and a range(L, R). The task is to find the number of subarrays having sum in the range L to R (inclusive).
Example 1:
Input:
N = 3, L = 3, R = 8
A[] = {1, 4, 6}
Output: 
3
Explanation: 
The subarrays are [1,4], [4] and [6]
Example 2:
Input:
N = 4, L = 4, R = 13
A[] = {2, 3, 5, 8}
Output: 
6
Explanation: 
The subarrays are [2,3], [2,3,5], 
[3,5],[5], [5,8] and [8]
Your Task: 
You don't need to read input or print anything. Complete the function countSubarray( ) which takes the integer N , the array A[], the integer L and the integer R as input parameters and returns the number of subarays. 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{6}
1 ≤ A[] ≤ 10^{9}
1 ≤ L ≤ R ≤ 10^{15}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Data structures

Amortized analysis

Starter code: #User function Template for python3
class Solution:
    def countSubarray(self, N, A, L, R):
        # code here

Solutions:
class Solution:

	def countSub(self, arr, n, x):
		st = 0
		end = 0
		sum = 0
		cnt = 0
		while end < n:
			sum += arr[end]
			while st <= end and sum > x:
				sum -= arr[st]
				st += 1
			cnt += end - st + 1
			end += 1
		return cnt

	def countSubarray(self, N, A, L, R):
		Rcnt = self.countSub(A, N, R)
		Lcnt = self.countSub(A, N, L - 1)
		return Rcnt - Lcnt


class Solution:

	def countSubarray(self, n, a, l, r):

		def sumlessthanequalto(x):
			start = 0
			end = 0
			sum_ = 0
			count = 0
			while end < n:
				sum_ += a[end]
				while sum_ > x and start <= end:
					sum_ -= a[start]
					start += 1
				if start <= end:
					count += end - start + 1
				end += 1
			return count
		return sumlessthanequalto(r) - sumlessthanequalto(l - 1)


class Solution:

	def countSubarray(self, N, A, L, R):
		self.N = N
		self.A = A
		self.L = L
		self.R = R
		rs = self.sum(R)
		ls = self.sum(L - 1)
		return rs - ls

	def sum(self, ele):
		c = 0
		su = 0
		ws = 0
		for i in range(self.N):
			if c + self.A[i] > ele:
				while c + self.A[i] > ele and ws < i:
					su += i - ws
					c -= self.A[ws]
					ws += 1
			if self.A[i] <= ele:
				c += self.A[i]
			if A[i] > ele:
				ws = i + 1
		k = N - ws
		return su + k * (k + 1) // 2


class Solution:

	def countSubarray(self, N, A, L, R):
		prefix = [0] * (N + 1)
		for i in range(1, N + 1):
			prefix[i] = prefix[i - 1] + A[i - 1]

		def countSubarraysWithSumAtMost(x):
			ans = 0
			j = 0
			for i in range(1, N + 1):
				while prefix[i] - prefix[j] > x:
					j += 1
				ans += i - j
			return ans
		return countSubarraysWithSumAtMost(R) - countSubarraysWithSumAtMost(L - 1)


class Solution:

	def countSubarray(self, N, A, L, R):
		ans1 = self.help(N, A, L - 1)
		ans2 = self.help(N, A, R)
		return ans2 - ans1

	def help(self, N, A, K):
		ans = 0
		sum_ = 0
		l = 0
		for r in range(len(A)):
			sum_ += A[r]
			while sum_ > K:
				sum_ -= A[l]
				l += 1
			ans += r - l + 1
		return ans


class Solution:

	def countSubarray(self, N, A, L, R):
		left = 0
		su = 0
		count1 = 0
		for right in range(0, N):
			su += A[right]
			while su > L - 1:
				su -= A[left]
				left += 1
			count1 += right - left + 1
		count2 = 0
		su2 = 0
		left1 = 0
		for right1 in range(0, N):
			su2 += A[right1]
			while su2 > R:
				su2 -= A[left1]
				left1 += 1
			count2 += right1 - left1 + 1
		if count2 >= count1:
			return count2 - count1
		return count1 - count2


class Solution:

	def countSubarray(self, N, A, L, R):

		def count_sub(A, k):
			c = 0
			(left, right) = (0, 0)
			sum = 0
			while right < N:
				if sum + A[right] <= k:
					sum += A[right]
					c += right - left + 1
					right += 1
				else:
					sum -= A[left]
					left += 1
			return c
		c1 = count_sub(A, R)
		c2 = count_sub(A, L - 1)
		return c1 - c2


class Solution:

	def countSubarray(self, N, A, L, R):

		def count_subarrays(A, K):
			c = 0
			(left, right) = (0, 0)
			sum = 0
			while right < N:
				if sum + A[right] <= K:
					sum += A[right]
					c += right - left + 1
					right += 1
				else:
					sum -= A[left]
					left += 1
			return c
		c1 = count_subarrays(A, R)
		c2 = count_subarrays(A, L - 1)
		return c1 - c2


class Solution:

	def countSubarray(self, N, A, L, R):

		def sumlessthanequalto(x):
			i = 0
			j = 0
			count = 0
			sum = 0
			while j < N:
				sum += A[j]
				while i <= j and sum > x:
					sum -= A[i]
					i += 1
				if i <= j:
					count += j - i + 1
				j += 1
			return count
		return sumlessthanequalto(R) - sumlessthanequalto(L - 1)


class Solution:

	def countSub(self, N, A, V):
		tot = 0
		ans = 0
		l = 0
		for r in range(N):
			tot += A[r]
			while tot > V:
				tot -= A[l]
				l += 1
			ans += r - l + 1
		return ans

	def countSubarray(self, N, A, L, R):
		return self.countSub(N, A, R) - self.countSub(N, A, L - 1)


class Solution:

	def countSubarray(self, N, A, L, R):
		one = self.sub(A, N, L - 1)
		two = self.sub(A, N, R)
		return two - one

	def sub(self, A, N, X):
		sums = 0
		i = 0
		j = 0
		ans = 0
		while i < N:
			sums += A[i]
			while sums > X:
				sums -= A[j]
				j += 1
			ans += i - j + 1
			i += 1
		return ans


class Solution:

	def countSubarray(self, N, A, L, R):
		return Solution.counter(A, R, N) - Solution.counter(A, L - 1, N)

	def counter(A, lim, N):
		i = ans = summ = 0
		for x in range(N):
			summ += A[x]
			while summ > lim:
				summ -= A[i]
				i += 1
			ans += x - i + 1
		return ans


class Solution:

	def countSubarray(self, N, A, L, R):
		ans1 = self.count(N, A, L - 1)
		ans2 = self.count(N, A, R)
		return ans2 - ans1

	def count(self, N, A, X):
		ans = 0
		sums = 0
		j = 0
		for i in range(N):
			sums += A[i]
			while sums > X:
				sums -= A[j]
				j += 1
			ans += i - j + 1
		return ans


class Solution:

	def countSubarray(self, N, A, L, R):

		def helper(n, arr, num):
			start = 0
			ans = 0
			Sum = 0
			for end in range(n):
				Sum += arr[end]
				while Sum > num:
					Sum -= arr[start]
					start += 1
				ans += end - start + 1
			return ans
		return helper(N, A, R) - helper(N, A, L - 1)


class Solution:

	def countSubarray(self, N, A, L, R):

		def sumlessthanequalto(x):
			start = 0
			(end, s) = (0, 0)
			count = 0
			while end < N:
				s += A[end]
				while s > x and start <= end:
					s -= A[start]
					start += 1
				if start <= end:
					count += end - start + 1
				end += 1
			return count
		return sumlessthanequalto(R) - sumlessthanequalto(L - 1)


class Solution:

	def Countsub(self, arr, n, x):
		(st, end) = (0, 0)
		cnt = 0
		sum = 0
		while end < n:
			sum += arr[end]
			while st <= end and sum > x:
				sum -= arr[st]
				st += 1
			cnt += end - st + 1
			end += 1
		return cnt

	def countSubarray(self, N, A, L, R):
		rcnt = self.Countsub(A, N, R)
		lcnt = self.Countsub(A, N, L - 1)
		return rcnt - lcnt


def countsub(arr, su):
	start = 0
	c = 0
	csum = 0
	for i in range(len(arr)):
		csum += arr[i]
		while csum > su:
			csum -= arr[start]
			start += 1
		c += i - start + 1
	return c

class Solution:

	def countSubarray(self, N, A, L, R):
		return countsub(A, R) - countsub(A, L - 1)


class Solution:

	def countSubarray(self, N, A, L, R):

		def sumCal(x):
			start = 0
			end = 0
			cnt = 0
			tot = 0
			while end < N:
				tot += A[end]
				while tot > x and start <= end:
					tot -= A[start]
					start += 1
				if start <= end:
					cnt += end - start + 1
				end += 1
			return cnt
		return sumCal(R) - sumCal(L - 1)


import bisect

class Solution:

	def countSubarray(self, N, A, L, R):
		(l, r) = (0, 0)
		(sum1, count1, count2) = (0, 0, 0)
		while r < N:
			sum1 += A[r]
			while sum1 > R:
				sum1 -= A[l]
				l += 1
			count1 += r - l + 1
			r += 1
		sum1 = r = l = 0
		while r < N:
			sum1 += A[r]
			while sum1 > L - 1:
				sum1 -= A[l]
				l += 1
			count2 += r - l + 1
			r += 1
		return count1 - count2


class Solution:

	def count(self, n, a, x):
		ans = 0
		summ = 0
		l = 0
		for i in range(n):
			summ += a[i]
			while summ > x:
				summ -= a[l]
				l += 1
			ans += i - l + 1
		return ans

	def countSubarray(self, n, arr, l, r):
		temp1 = self.count(n, arr, r)
		temp2 = self.count(n, arr, l - 1)
		return temp1 - temp2


class Solution:

	def helper(self, x, a, n):
		start = 0
		end = 0
		sum_ = 0
		count = 0
		while end < n:
			sum_ += a[end]
			while sum_ > x and start <= end:
				sum_ -= a[start]
				start += 1
			if start <= end:
				count += end - start + 1
			end += 1
		return count

	def countSubarray(self, N, A, L, R):
		return self.helper(R, A, N) - self.helper(L - 1, A, N)


class Solution:

	def countSubarray(self, N, A, L, R):

		def check(arr, bound):
			l = 0
			sm = 0
			ans = 0
			for r in range(len(arr)):
				sm += arr[r]
				while sm > bound:
					sm -= arr[l]
					l += 1
				ans += r - l + 1
			return ans
		a = check(A, L - 1)
		b = check(A, R)
		return abs(a - b)


class Solution:

	def solve(self, A, R):
		i = j = s = c = 0
		n = len(A)
		while j < n:
			s += A[j]
			while s > R:
				s -= A[i]
				i += 1
			c += j - i + 1
			j += 1
		return c

	def countSubarray(self, N, A, L, R):
		c = self.solve(A, L - 1)
		c1 = self.solve(A, R)
		return abs(c - c1)


class Solution:

	def countSubarray(self, n, arr, l, r):
		sl = [0]
		total = 0
		ans = 0
		i = j = -1
		for num in arr:
			total += num
			while i + 1 < len(sl) and sl[i + 1] < total - r:
				i += 1
			while j + 1 < len(sl) and sl[j + 1] <= total - l:
				j += 1
			ans += j - i
			sl.append(total)
		return ans


class Solution:

	def countone(self, N, A, x):
		st = 0
		end = 0
		cnt = 0
		summ = 0
		while end < N:
			summ += A[end]
			while st <= end and summ > x:
				summ -= A[st]
				st += 1
			cnt += end - st + 1
			end += 1
		return cnt

	def countSubarray(self, N, A, L, R):
		Lcnt = self.countone(N, A, L - 1)
		Rcnt = self.countone(N, A, R)
		ans = abs(Rcnt - Lcnt)
		return ans


class Solution:

	def countSubarray(self, n, x, L, R):

		def f(e):
			i = 0
			s = 0
			ans = 0
			for j in range(n):
				s += x[j]
				while s > e:
					ans += j - i
					s -= x[i]
					i += 1
			while i < n:
				ans += n - i
				i += 1
			return ans
		return f(R) - f(L - 1)


class Solution:

	def countSubarray(self, N, A, L, R):
		pre = [0] * (N + 1)
		for i in range(1, N + 1):
			pre[i] = pre[i - 1] + A[i - 1]
		ans = 0
		left = 0
		right = 0
		left_sum = 0
		right_sum = 0
		sumi = 0
		for i in range(N):
			left_sum -= sumi
			right_sum -= sumi
			while left < N and left_sum < L:
				left_sum += A[left]
				left += 1
			if left_sum < L:
				break
			while right < N and right_sum <= R:
				right_sum += A[right]
				right += 1
			ans += right - left
			if right == N and right_sum >= L and (right_sum <= R):
				ans += 1
			sumi = A[i]
		return ans


def count(N, A, R):
	total = A[0]
	end = beg = 0
	cases = 0
	while end < N and beg < N:
		if total <= R:
			end += 1
			if end >= beg:
				cases += end - beg
			if end < N:
				total += A[end]
		else:
			total -= A[beg]
			beg += 1
	return cases

class Solution:

	def countSubarray(self, N, A, L, R):
		return count(N, A, R) - count(N, A, L - 1)


class Solution:

	def solve(self, arr, x):
		left = 0
		right = 0
		curr = 0
		res = 0
		n = len(arr)
		while right < n and left < n:
			curr += arr[right]
			while curr > x:
				curr -= arr[left]
				left += 1
			res += right - left + 1
			right += 1
		return res

	def countSubarray(self, n, a, l, r):
		return self.solve(a, r) - self.solve(a, l - 1)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, L, R) = map(int, input().strip().split())
		A = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.countSubarray(N, A, L, R)
		print(ans)


class Solution:

	def countSubarray(self, n, a, l, r):

		def sumlessthanequalto(x):
			start = 0
			end = 0
			sum_ = 0
			count = 0
			while end < n:
				sum_ += a[end]
				while sum_ > x and start <= end:
					sum_ -= a[start]
					start += 1
				if start <= end:
					count += end - start + 1
				end += 1
			return count
		return sumlessthanequalto(r) - sumlessthanequalto(l - 1)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, L, R) = map(int, input().strip().split())
		A = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.countSubarray(N, A, L, R)
		print(ans)


class Solution:

	def countSubarray(self, N, A, L, R):
		s = 0
		d = {}
		ans1 = 0
		arr = A
		i = 0
		pi = 0
		while i < N:
			s += arr[i]
			if s <= R:
				ans1 += i - pi + 1
			else:
				while s > R:
					s -= arr[pi]
					pi += 1
				ans1 += i - pi + 1
			i += 1
		i = 0
		pi = 0
		ans2 = 0
		s = 0
		while i < N:
			s += arr[i]
			if s < L:
				ans2 += i - pi + 1
			else:
				while s >= L:
					s -= arr[pi]
					pi += 1
				ans2 += i - pi + 1
			i += 1
		return ans1 - ans2
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, L, R) = map(int, input().strip().split())
		A = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.countSubarray(N, A, L, R)
		print(ans)


class Solution:

	def countSubarray(self, N, A, L, R):

		def solve(x):
			i = 0
			j = 0
			Sum = 0
			count = 0
			while j < N:
				Sum = Sum + A[j]
				while Sum > x and i <= j:
					Sum = Sum - A[i]
					i = i + 1
				if i <= j:
					count += j - i + 1
				j = j + 1
			return count
		return solve(R) - solve(L - 1)


class Solution:

	def countSubarray(self, N, A, L, R):

		def helper(x):
			start = 0
			end = 0
			sum1 = 0
			count = 0
			while end < N:
				sum1 += A[end]
				while sum1 > x and start <= end:
					sum1 -= A[start]
					start += 1
				if start <= end:
					count += end - start + 1
				end += 1
			return count
		return helper(R) - helper(L - 1)


class Solution:

	def countSubarray(self, n, a, L, R):

		def count_sub(a, x, n):
			sum = 0
			start = 0
			end = 0
			count = 0
			while end < n:
				sum += a[end]
				while start <= end and sum > x:
					sum -= a[start]
					start += 1
				count += end - start + 1
				end += 1
			return count
		return count_sub(a, R, n) - count_sub(a, L - 1, n)


def countless(n, a, x):
	ans = 0
	s = 0
	(i, j) = (0, 0)
	while i < n:
		s += a[i]
		while s > x and j <= i:
			s -= a[j]
			j += 1
		ans += i - j + 1
		i += 1
	return ans

class Solution:

	def countSubarray(self, n, a, l, r):
		return countless(n, a, r) - countless(n, a, l - 1)


class Solution:

	def countSubarray(self, N, A, L, R):
		(l, r, count1) = (0, 0, 0)
		m = 0
		for r in range(0, N):
			m += A[r]
			while l < r and m > R:
				m -= A[l]
				l += 1
			if m <= R:
				le = r - l + 1
				count1 += le
		(l, r, count2) = (0, 0, 0)
		m = 0
		for r in range(0, N):
			m += A[r]
			while l < r and m > L - 1:
				m -= A[l]
				l += 1
			if m <= L - 1:
				le = r - l + 1
				count2 += le
		return count1 - count2


class Solution:

	def countSubarray(self, N, A, L, R):
		r_cnt = self.getSubarrayCnt(N, A, R)
		l_cnt = self.getSubarrayCnt(N, A, L - 1)
		return r_cnt - l_cnt

	def getSubarrayCnt(self, n, a, x):
		start = 0
		end = 0
		count = 0
		cur_sum = 0
		while end < n:
			cur_sum += a[end]
			while start <= end and cur_sum > x:
				cur_sum -= a[start]
				start += 1
			count += end - start + 1
			end += 1
		return count


class Solution:

	def helper(self, nums, k):
		l = 0
		r = 0
		res = 0
		n = len(nums)
		ans = 0
		while r < n:
			res += nums[r]
			while res > k:
				res -= nums[l]
				l += 1
			ans += r - l + 1
			r += 1
		return ans

	def countSubarray(self, N, A, L, R):
		return self.helper(A, R) - self.helper(A, L - 1)


class Solution:

	def cnt(self, N, A, X):
		c = 0
		s = 0
		l = r = 0
		for r in range(0, N):
			s += A[r]
			while s > X:
				s -= A[l]
				l += 1
			c += r - l + 1
		return c

	def countSubarray(self, N, A, L, R):
		return self.cnt(N, A, R) - self.cnt(N, A, L - 1)


class Solution:

	def countSubarray(self, N, A, L, R):
		return self.countSub(N, A, R) - self.countSub(N, A, L - 1)

	def countSub(self, N, A, k):
		count = 0
		Sum = 0
		end = 0
		start = 0
		while end < N:
			Sum += A[end]
			while start <= end and Sum > k:
				Sum -= A[start]
				start += 1
			count += end - start + 1
			end += 1
		return count


class Solution:

	def countSubarray(self, n, arr, left, right):

		def countSubaarraysSumLessThanX(arr, x):
			addition = 0
			(left, right) = (0, 0)
			count = 0
			while right < len(arr):
				addition += arr[right]
				while addition > x:
					addition -= arr[left]
					left += 1
				count += right - left + 1
				right += 1
			return count
		return countSubaarraysSumLessThanX(arr, right) - countSubaarraysSumLessThanX(arr, left - 1)


class Solution:

	def solve(self, A, N, a):
		j = 0
		su = 0
		ans = 0
		for i in range(N):
			su += A[i]
			while su > a:
				su -= A[j]
				j += 1
			ans += i - j + 1
		return ans

	def countSubarray(self, N, A, L, R):
		return self.solve(A, N, R) - self.solve(A, N, L - 1)


class Solution:

	def countSubarray(self, N, A, L, R):

		def countWhole(a, n, k):
			i = 0
			j = 0
			s = 0
			c = 0
			while j < n:
				s = s + a[j]
				while s > k:
					s = s - a[i]
					i = i + 1
				c = c + j - i + 1
				j = j + 1
			return c
		return countWhole(A, N, R) - countWhole(A, N, L - 1)


class Solution:

	def countSubarray(self, N, A, L, R):

		def kadane(A, N, val):
			cur_sum = 0
			left = 0
			ans = 0
			for i in range(N):
				cur_sum += A[i]
				if cur_sum > val:
					while cur_sum > val:
						cur_sum -= A[left]
						left += 1
				ans += i - left + 1
			return ans
		a1 = kadane(A, N, R)
		a2 = kadane(A, N, L - 1)
		return a1 - a2


def subArraySum(arr, n, s):
	summ = 0
	i = 0
	j = 0
	count = 0
	while j < n:
		summ = summ + arr[j]
		while summ > s:
			summ = summ - arr[i]
			i = i + 1
		count = count + (j - i) + 1
		j = j + 1
	return count

class Solution:

	def countSubarray(self, N, A, L, R):
		rsubarray = subArraySum(A, N, R)
		lsubarray = subArraySum(A, N, L - 1)
		return rsubarray - lsubarray


class Solution:

	def countSubarray(self, N, A, L, R):
		sumL = 0
		sumM = 0
		res = 0
		l = 0
		r = 0
		m = 0
		while r < N and sumL + A[r] < L:
			sumL += A[r]
			r += 1
		sumM = sumL
		while r < N:
			sumL += A[r]
			sumM += A[r]
			while sumL > R:
				sumL -= A[l]
				l += 1
			while sumM - A[m] >= L:
				sumM -= A[m]
				m += 1
			res += m - l + 1
			r += 1
		return res


class Solution:

	def countSubarray(self, N, arr, L, R):
		(i, j) = (0, 0)
		(s1, c1) = (0, 0)
		while j < len(arr):
			s1 = s1 + arr[j]
			if s1 <= R:
				j += 1
				c1 += j - i
			else:
				while s1 > R:
					s1 -= arr[i]
					i += 1
				s1 -= arr[j]
		(i, j) = (0, 0)
		(s2, c2) = (0, 0)
		while j < len(arr):
			s2 = s2 + arr[j]
			if s2 <= L - 1:
				j += 1
				c2 += j - i
			else:
				while s2 > L - 1:
					s2 -= arr[i]
					i += 1
				s2 -= arr[j]
		return c1 - c2


class Solution:

	def countSubarray(self, N, arr, L, R):
		x = self.t_L(arr, L)
		y = self.t_R(arr, R)
		return y - x

	def t_R(self, arr, R):
		(i, j, tmp, ans) = (0, 0, 0, 0)
		while j < len(arr):
			tmp += arr[j]
			if tmp <= R:
				j += 1
				ans += j - i
			else:
				while tmp > R:
					tmp -= arr[i]
					i += 1
				tmp -= arr[j]
		return ans

	def t_L(self, arr, L):
		(i, j, tmp, ans) = (0, 0, 0, 0)
		while j < len(arr):
			tmp += arr[j]
			if tmp < L:
				j += 1
				ans += j - i
			else:
				while tmp >= L:
					tmp -= arr[i]
					i += 1
				tmp -= arr[j]
		return ans


class Solution:

	def countSubarray(self, N, A, L, R):
		ans = 0
		(l, r, s) = (0, 0, 0)
		while r < N:
			s += A[r]
			while l <= r and s > R:
				s -= A[l]
				l += 1
			ans += r - l + 1
			r += 1
		r = 0
		l = 0
		s = 0
		while r < N:
			s += A[r]
			while l <= r and s >= L:
				s -= A[l]
				l += 1
			ans -= r - l + 1
			r += 1
		return ans


class Solution:

	def countSubarray(self, N, A, L, R):

		def help(n, a, r):
			st = 0
			ans = 0
			sum = 0
			for i in range(n):
				sum += a[i]
				while sum > r:
					sum -= a[st]
					st += 1
				ans += i - st + 1
			return ans
		return help(N, A, R) - help(N, A, L - 1)


class Solution:

	def countSubarray(self, N, A, L, R):
		i = 0
		sum1 = 0
		count1 = 0
		for j in range(N):
			sum1 += A[j]
			while i <= j and sum1 > R:
				sum1 -= A[i]
				i += 1
			count1 += j - i + 1
		i = sum1 = count2 = 0
		for j in range(N):
			sum1 += A[j]
			while i <= j and sum1 > L - 1:
				sum1 -= A[i]
				i += 1
			count2 += j - i + 1
		return count1 - count2


class Solution:

	def countSubarray(self, N, A, L, R):
		i = j1 = j2 = 0
		sum1 = sum2 = ans = 0
		while i < N:
			while j1 < N and sum1 + A[j1] < L:
				sum1 += A[j1]
				j1 += 1
			if not j2:
				sum2 = sum1
				j2 = j1
			while j2 < N and sum2 + A[j2] <= R:
				sum2 += A[j2]
				j2 += 1
			ans += j2 - j1
			sum1 -= A[i]
			sum2 -= A[i]
			i += 1
		return ans


class Solution:

	def countSubarray(self, N, A, L, R):
		rcnt = self.countSubArr(A, N, R)
		lcnt = self.countSubArr(A, N, L - 1)
		return rcnt - lcnt

	def countSubArr(self, A, N, X):
		start = 0
		end = 0
		sum = 0
		count = 0
		while end < N:
			sum += A[end]
			while start <= end and sum > X:
				sum -= A[start]
				start += 1
			count += end - start + 1
			end += 1
		return count


class Solution:

	def countSubarray(self, N, A, L, R):
		c1 = 0
		total = 0
		l = 0
		r = 0
		while r < N:
			total += A[r]
			if total >= L:
				while total >= L and l <= r:
					total -= A[l]
					l += 1
			c1 += r - l + 1
			r += 1
		c2 = 0
		total = 0
		l = 0
		r = 0
		while r < N:
			total += A[r]
			if total > R:
				while total > R and l <= r:
					c2 += N - r
					total -= A[l]
					l += 1
			r += 1
		total_subarray = N * (N + 1) // 2
		ans = total_subarray - (c1 + c2)
		return ans


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

def countSubs(a, val):
	(ans, p1, p2, sm) = (0, 0, 0, a[0])
	n = len(a)
	while p1 < n and p2 < n:
		if sm < val:
			p2 += 1
			if p2 >= p1:
				ans += p2 - p1
			if p2 < n:
				sm += a[p2]
		else:
			sm -= a[p1]
			p1 += 1
	return ans

class Solution:

	def countSubarray(self, N, A, L, R):
		sumLessThanR = countSubs(A, R + 1)
		sumLessThanL = countSubs(A, L)
		return sumLessThanR - sumLessThanL


class Solution:

	def countSubarray(self, N, A, L, R):

		def count(A, limit, N):
			(i, j, s, ans) = (0, 0, 0, 0)
			while j < N:
				s = s + A[j]
				while s > limit:
					s = s - A[i]
					i = i + 1
				ans = ans + j - i + 1
				j = j + 1
			return ans
		return count(A, R, N) - count(A, L - 1, N)


class Solution:

	def countsub(self, arr, n, x):
		(start, end, sumi, ans) = (0, 0, 0, 0)
		for end in range(0, n):
			sumi += arr[end]
			while sumi > x:
				sumi -= arr[start]
				start += 1
			ans += end - start + 1
		return ans

	def countSubarray(self, N, A, L, R):
		rt = self.countsub(A, N, R)
		lt = self.countsub(A, N, L - 1)
		return rt - lt


class Solution:

	def countSubarray(self, N, A, L, R):
		RCount = self.countSubLT(A, R)
		LCount = self.countSubLT(A, L - 1)
		return RCount - LCount

	def countSubLT(self, A, X):
		N = len(A)
		end = 0
		start = 0
		sum = 0
		subArrayCount = 0
		while end < N:
			sum += A[end]
			while start <= end and sum > X:
				sum -= A[start]
				start += 1
			subArrayCount += end - start + 1
			end += 1
		return subArrayCount