Given an array of N elements and L and R, print the number of sub-arrays such that the value of the maximum array element in that subarray is at least L and at most R.
Example 1:
Input : Arr[] = {2, 0, 11, 3, 0}
L = 1 and R = 10
Output : 4
Explanation:
The sub-arrays {2}, {2, 0}, {3} and {3, 0}
have maximum in range 1-10.
Example 2:
Input : Arr[] = {3, 4, 1}
L = 2 and R = 4
Output : 5
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function countSubarrays() that takes an array (arr), sizeOfArray (n), element L, integer R, and return the number of subarray with the maximum in range L-R. The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ L ≤ R ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Amortized analysis

Starter code: #User function Template for python3

class Solution:
    def countSubarrays(self, a,n,L,R): 
        # Complete the function

Solutions:
def mgc(n):
	return n * (n + 1) // 2

class Solution:

	def countSubarrays(self, a, n, L, R):
		(fp, lp) = (0, 0)
		ans = 0
		prev = 0
		while lp < n:
			if a[lp] >= L and a[lp] <= R:
				prev = lp - fp + 1
			elif a[lp] > R:
				prev = 0
				fp = lp + 1
			lp += 1
			ans += prev
		return ans


class Solution:

	def countSubarrays(self, nums, a, left, right):
		ans = 0
		cnt = 0
		i = 0
		j = 0
		while i < a:
			if nums[i] >= left and nums[i] <= right:
				cnt = i - j + 1
				ans += cnt
			elif nums[i] < left:
				ans += cnt
			elif nums[i] > right:
				cnt = 0
				j = i + 1
			i += 1
		return ans


class Solution:

	def countSubarrays(self, nums, a, left, right):

		def count(bound):
			ans = cnt = 0
			for x in nums:
				if x <= bound:
					cnt = cnt + 1
				else:
					cnt = 0
				ans += cnt
			return ans
		return count(right) - count(left - 1)


class Solution:

	def countSubarrays(self, a, n, L, R):
		ans = 0
		maxele = -999999
		maxind = -1
		cnt = 0
		for i in range(n):
			if a[i] >= L and a[i] <= R:
				cnt = 0
				ans += i - maxind
			elif a[i] > R:
				cnt = 0
				maxind = i
			else:
				cnt += 1
				ans += i - maxind - cnt
		return ans


class Solution:

	def countSubarrays(self, a, n, L, R):
		(wind, count, i, j) = (0, 0, 0, 0)
		while j < n:
			if a[j] >= L and a[j] <= R:
				wind = j - i + 1
			elif a[j] > R:
				wind = 0
				i = j + 1
			count += wind
			j += 1
		return count


class Solution:

	def countSubarrays(self, a, n, L, R):
		(left, right) = (-1, -1)
		idx = 0
		ans = 0
		while idx < n:
			cur = a[idx]
			if L <= cur <= R:
				right = idx
			elif cur > R:
				(left, right) = (idx, idx)
			ans += right - left
			idx += 1
		return ans


class Solution:

	def countSubarrays(self, a, n, L, R):
		right = -1
		start = -1
		i = 0
		ans = 0
		while i < n:
			cur = a[i]
			if L <= cur <= R:
				right = i
			elif cur > R:
				start = i
				right = i
			ans += right - start
			i += 1
		return ans


class Solution:

	def countSubarrays(self, a, n, L, R):
		cur_max = 0
		cur_max_idx = -1
		right_most_range = 0
		start = -1
		i = 0
		ans = 0
		while i < n:
			cur = a[i]
			if L <= cur <= R:
				right_most_idx = i
			if cur_max < cur:
				cur_max = cur
				cur_max_idx = i
			if cur_max > R:
				start = i
				cur_max = 0
				cur_max_idx = i
				right_most_range = i
			elif L <= cur_max <= R:
				ans += right_most_idx - start
			i += 1
		return ans


class Solution:

	def countSubarrays(self, a, n, L, R):
		ans = 0
		sub = 0
		start = 0
		for end in range(n):
			if arr[end] >= L and arr[end] <= R:
				sub = end - start + 1
			if arr[end] > R:
				sub = 0
				start = end + 1
			ans += sub
		return ans


class Solution:

	def countSubarrays(self, a, n, L, R):
		i = 0
		j = 0
		count = 0
		result = 0
		while j < len(a):
			if L <= a[j] <= R:
				result = j - i + 1
			if a[j] > R:
				result = 0
				i = j + 1
			count = count + result
			j = j + 1
		return count


class Solution:

	def countSubarrays(self, a, n, L, R):
		i = 0
		j = 0
		count = 0
		m = 0
		while j < n:
			if a[j] > R:
				m = 0
				i = j + 1
			elif a[j] in range(L, R + 1):
				m = j - i + 1
			j += 1
			count += m
		return count


class Solution:

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

	def countSubarrays(self, a, n, L, R):
		l = 0
		r = 0
		ans = 0
		for i in range(n):
			if a[i] < L:
				l += 1
				r += 1
			elif a[i] > R:
				ans += Solution.code(l) - Solution.code(r)
				l = 0
				r = 0
			else:
				ans -= Solution.code(r)
				r = 0
				l += 1
		ans += Solution.code(l) - Solution.code(r)
		return ans


class Solution:

	def countSubarrays(self, arr, n, L, R):
		ans = 0
		prevcnt = 0
		(s, e) = (0, 0)
		while e <= n - 1:
			if L <= arr[e] and arr[e] <= R:
				ans += e - s + 1
				prevcnt = e - s + 1
			elif arr[e] < L:
				ans += prevcnt
			elif arr[e] > R:
				s = e + 1
				prevcnt = 0
			e += 1
		return ans


class Solution:

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

		def sub(n):
			return n * (n + 1) // 2
		res = 0
		inc = 0
		exc = 0
		for i in range(len(a)):
			if arr[i] > R:
				res = res + (sub(inc) - sub(exc))
				inc = 0
				exc = 0
			elif arr[i] < L:
				inc += 1
				exc += 1
			else:
				res = res - sub(exc)
				inc += 1
				exc = 0
		res = res + (sub(inc) - sub(exc))
		return res


class Solution:

	def countSubarrays(self, nums, n, left, right):
		i = 0
		j = 0
		c = 0
		m = 0
		while j < len(nums):
			if nums[j] > r:
				m = 0
				i = j + 1
			elif nums[j] >= left and nums[j] <= right:
				m = j - i + 1
			c += m
			j += 1
		return c


class Solution:

	def countSubarrays(self, a, n, L, R):
		ans = 0
		st = 0
		build = 0
		for i in range(n):
			if L <= a[i] <= R:
				build = i - st + 1
			elif a[i] > R:
				build = 0
				st = i + 1
			ans += build
		return ans


class Solution:

	def countSubarrays(self, arr, n, L, R):
		(i, j) = (0, 0)
		count = 0
		m = 0
		while j < n:
			if arr[j] >= L and arr[j] <= R:
				m = j - i + 1
			elif arr[j] > R:
				m = 0
				i = j + 1
			count += m
			j += 1
		return count


class Solution:

	def countSubarrays(self, a, n, L, R):
		c = 0
		(i, j, k) = (0, 0, 0)
		while j < n:
			if a[j] > R:
				k = 0
				i = j + 1
			elif a[j] >= L and a[j] <= R:
				k = j - i + 1
			c += k
			j += 1
		return c


from collections import deque

class Solution:

	def countSubarrays(self, arr, n, l, r):
		dp = [0] * n
		q = deque()
		for i in range(n):
			while q and arr[q[-1]] <= arr[i]:
				q.pop()
			if not q:
				dp[i] = (i + 1) * int(l <= arr[i] <= r)
			else:
				dp[i] = (i - q[-1]) * int(l <= arr[i] <= r) + dp[q[-1]]
			q.append(i)
		return sum(dp)


class Solution:

	def countSubarrays(self, nums, n, left, right):
		(n, l, valid, res) = (len(nums), 0, 0, 0)
		for r in range(0, n):
			if left <= nums[r] <= right:
				valid = r - l + 1
			if nums[r] > right:
				l = r + 1
				valid = 0
			res += valid
		return res


class Solution:

	def countSubarrays(self, a, n, L, R):
		e = 0
		r = 0
		g = -1
		k = -1
		for i in range(n):
			if arr[i] > R:
				e = 0
				g = -1
				k = -1
			elif arr[i] < L:
				if e != 0 and k != -1:
					r += k - g + 1
				e += 1
				if g == -1:
					g = i
			if arr[i] >= L and arr[i] <= R:
				r += 1 + e
				e += 1
				if g == -1:
					g = i
				k = i
		return r
for _ in range(0, int(input())):
	(n, l, r) = map(int, input().strip().split())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	v = ob.countSubarrays(arr, n, l, r)
	print(v)


class Solution:

	def countSubarrays(self, a, n, L, R):
		i = 0
		it = 0
		et = 0
		ans = 0
		c = 0
		p = False
		while i < n:
			if a[i] >= L and a[i] <= R:
				ans -= et * (et + 1) // 2
				it += 1
				et = 0
			elif a[i] < L:
				it += 1
				et += 1
			else:
				ans += it * (it + 1) // 2 - et * (et + 1) // 2
				it = 0
				et = 0
			i += 1
		ans += it * (it + 1) // 2 - et * (et + 1) // 2
		return ans
for _ in range(0, int(input())):
	(n, l, r) = map(int, input().strip().split())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	v = ob.countSubarrays(arr, n, l, r)
	print(v)


class Solution:

	def countSubarrays(self, arr, n, L, R):
		rem = inc = c = 0
		for i in range(n):
			if arr[i] < L:
				rem += 1
				inc += 1
			elif L <= arr[i] <= R:
				c -= rem * (rem + 1) >> 1
				rem = 0
				inc += 1
			if arr[i] > R:
				c += (inc * (inc + 1) >> 1) - (rem * (rem + 1) >> 1)
				rem = inc = 0
		c += (inc * (inc + 1) >> 1) - (rem * (rem + 1) >> 1)
		return c
for _ in range(0, int(input())):
	(n, l, r) = map(int, input().strip().split())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	v = ob.countSubarrays(arr, n, l, r)
	print(v)


class Solution:

	def countSubarrays(self, a, n, L, R):
		i = j = 0
		ans = curr = 0
		while j < n:
			if a[j] >= L and a[j] <= R:
				curr = j - i + 1
			if a[j] > R:
				curr = 0
				i = j + 1
			ans += curr
			j += 1
		return ans


class Solution:

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

		def maxlessthanequalto(x):
			max_so_far = 0
			end = start = 0
			count = 0
			while end < n:
				if a[end] <= x:
					count += end - start + 1
					end += 1
				else:
					end = end + 1
					start = end
			return count
		return maxlessthanequalto(R) - maxlessthanequalto(L - 1)


class Solution:

	def countSubarrays(self, a, n, L, R):
		start = 0
		count = 0
		sub_count = 0
		for end in range(n):
			if a[end] >= L and a[end] <= R:
				sub_count = end - start + 1
			elif a[end] > R:
				start = end + 1
				sub_count = 0
			count += sub_count
		return count


class Solution:

	def count_sub_array(self, n):
		return n * (n + 1) // 2 if n else 0

	def countSubarrays(self, a, n, L, R):
		less_tha_l = 0
		total = 0
		ans = 0
		for i in range(n):
			if a[i] > R:
				ans += self.count_sub_array(total) - self.count_sub_array(less_tha_l)
				less_tha_l = 0
				total = 0
			elif a[i] < L:
				less_tha_l += 1
				total += 1
			else:
				ans = ans - self.count_sub_array(less_tha_l)
				less_tha_l = 0
				total += 1
		ans += self.count_sub_array(total) - self.count_sub_array(less_tha_l)
		return ans


class Solution:

	def countSubarrays(self, a, n, l, r):
		(i, j, ans) = (-1, -1, 0)
		for k in range(n):
			if a[k] > r:
				(i, j) = (k, k)
			elif a[k] >= l and a[k] <= r:
				j = k
			ans += j - i
		return ans


class Solution:

	def countSubarrays(self, a, n, L, R):
		(gr, ls, temp) = (0, 0, 0)
		for i in range(n):
			if arr[i] <= r:
				gr += 1
			else:
				temp += gr * (gr + 1) // 2
				gr = 0
			if arr[i] < l:
				ls += 1
			else:
				temp -= ls * (ls + 1) // 2
				ls = 0
		temp -= ls * (ls + 1) // 2
		temp += gr * (gr + 1) // 2
		return temp


class Solution:

	def countSubarrays(self, nums, n, left, right):
		(start, count, window_len) = (0, 0, 0)
		for (end, num) in enumerate(nums):
			if left <= num <= right:
				window_len = end - start + 1
			elif num > right:
				window_len = 0
				start = end + 1
			count += window_len
		return count


class Solution:

	def countSubarrays(self, a, n, l, r):
		i = 0
		j = 0
		c = 0
		ans = 0
		while j < n:
			if a[j] >= l and a[j] <= r:
				c = j - i + 1
			if a[j] > r:
				i = j + 1
				c = 0
			ans += c
			j = j + 1
		return ans


class Solution:

	def f(self, n):
		return n * (n + 1) // 2

	def countSubarrays(self, arr, n, L, R):
		x = 0
		y = 0
		ans = 0
		for i in arr:
			if i > R:
				ans += self.f(x) - self.f(y)
				x = 0
				y = 0
			elif i < L:
				x += 1
				y += 1
			else:
				ans -= self.f(y)
				x += 1
				y = 0
		ans += self.f(x) - self.f(y)
		return ans


class Solution:

	def count(self, n):
		return n * (n + 1) // 2

	def countSubarrays(self, a, n, L, R):
		ans = 0
		x = 0
		y = 0
		for i in a:
			if i > R:
				ans += self.count(x) - self.count(y)
				x = 0
				y = 0
			elif i < L:
				x += 1
				y += 1
			else:
				ans -= self.count(y)
				x += 1
				y = 0
		ans += self.count(x) - self.count(y)
		return ans


class Solution:

	def countSubarrays(self, a, n, L, R):
		si = 0
		ans = 0
		prev = 0
		for ei in range(n):
			if l <= a[ei] <= R:
				prev = ei - si + 1
				ans += prev
			elif L > a[ei]:
				ans += prev
			else:
				prev = 0
				si = ei + 1
		return ans


class Solution:

	def countSubarrays(self, a, n, L, R):
		i0 = 0
		i1 = 0
		Rplus = 0
		Lminus = 0
		Lminus1 = 0
		res = 0
		for j in range(len(a)):
			if a[j] > R:
				Rplus += 1
			elif a[j] < L:
				Lminus += 1
				Lminus1 += 1
			while Rplus > 0:
				if a[i0] > R:
					Rplus -= 1
				elif a[i0] < L:
					Lminus -= 1
				i0 += 1
				if i0 > i1:
					if a[i1] < L:
						Lminus1 -= 1
					i1 += 1
			while i1 <= j and Lminus1 < j - i1 + 1:
				if a[i1] < L:
					Lminus1 -= 1
				i1 += 1
			res += i1 - i0
		return res


class Solution:

	def countSubarrays(self, a, n, L, R):
		res = 0
		N = n
		A = a
		start = 0
		count = 0
		for i in range(N):
			if A[i] >= L and A[i] <= R:
				count = i - start + 1
				res = res + i - start + 1
			elif A[i] < L:
				res = res + count
			else:
				count = 0
				start = i + 1
		return res


class Solution:

	def countSubarrays(self, a, n, L, R):
		res = 0
		count = 0
		i = 0
		for j in range(n):
			if L <= a[j] <= R:
				count = j - i + 1
				res += count
			elif a[j] < L:
				res += count
			elif a[j] > R:
				count = 0
				i = j + 1
		return res