We are given an array of integers and a range, we need to find whether the subarray which falls in this range has values in the form of a mountain or not. All values of the subarray are said to be in the form of a mountain if either all values are increasing or decreasing or first increasing and then decreasing. More formally a subarray [a1, a2, a3 … aN] is said to be in form of a mountain if there exists an integer K, 1 <= K <= N such that,
a1 <= a2 <= a3 .. <= aK >= a(K+1) >= a(K+2) …. >= aN
You have to process Q queries. In each query you are given two integer L and R, denoting starting and last index of the subarrays respectively.
Example 1:
Input:
N = 8
a[] = {2,3,2,4,4,6,3,2}
Q = 2
Queries = (0,2), (1,3)
Output:
Yes
No
Explanation: For L = 0 and R = 2, a0 = 2,
a1 = 3 and a2 = 2, since they are in the
valid order,answer is Yes.
For L = 1 and R = 3, a1 = 3, a2 = 2 and
a3 = 4, since a1 > a2 and a2 < a4 the
order isn't valid, hence the answer is
No.
Your Task:
Complete the function processQueries() which takes the array, size of array queries and number of queries as parameter. It should return a vector/ArrayList/array (depending upon language cpp/Java/Python) of boolean values, true if the subarray is in mountain form, false otherwise. The driver code will print "Yes" if the returned value is true, otherwise "No".
Expected Time Complexity: O(N + Q).
Expected Auxiliary Space: O(N).
Constraints:
1 <= N, Q <= 10^{5}
1 <= a[i] <= 10^{6}, for each valid i
0 <= L <= R <= N-1

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3


class Solution:
    def processqueries(self,arr,n,m,q):
        # code here

Solutions:
class Solution:

	def processqueries(self, arr, n, m, q):
		incre = [0] * n
		decre = [n - 1] * n
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				incre[i] = i
			else:
				incre[i] = incre[i - 1]
		for j in range(n - 2, -1, -1):
			if arr[j] > arr[j + 1]:
				decre[j] = j
			else:
				decre[j] = decre[j + 1]
		ans = []
		for val in q:
			if decre[val[0]] >= incre[val[1]]:
				ans.append('Yes')
			else:
				ans.append('No')
		return ans


class Solution:

	def processqueries(self, arr, n, m, q):
		l = [0] * n
		r = [0] * n
		l[0] = 0
		curr = 0
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				curr = i
			l[i] = curr
		r[n - 1] = n - 1
		curr2 = n - 1
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				curr2 = i
			r[i] = curr2
		a = []
		for i in range(m):
			t = q[i]
			if r[t[0]] >= l[t[1]]:
				a.append('Yes')
			else:
				a.append('No')
		return a


class Solution:

	def processqueries(self, arr, n, m, q):
		out = []
		inc = [0 for i in range(n)]
		dec = [0 for i in range(n)]
		incptr = 0
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				incptr = i
			inc[i] = incptr
		dec[n - 1] = n - 1
		i = n - 2
		decptr = n - 1
		while i >= 0:
			if arr[i] > arr[i + 1]:
				decptr = i
			dec[i] = decptr
			i -= 1
		for i in q:
			if dec[i[0]] >= inc[i[1]]:
				out.append('Yes')
			else:
				out.append('No')
		return out


class Solution:

	def processqueries(self, arr, n, m, q):
		left = [0] * n
		right = [n - 1] * n
		ans = []
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				left[i] = i
			else:
				left[i] = left[i - 1]
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				right[i] = i
			else:
				right[i] = right[i + 1]
		for query in q:
			start = query[0]
			end = query[1]
			if right[start] >= left[end]:
				ans.append('Yes')
			else:
				ans.append('No')
		return ans


class Solution:

	def processqueries(self, arr, n, m, q):
		l = [0] * n
		r = [n - 1] * n
		last_incr = 0
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				last_incr = i
			l[i] = last_incr
		first_decr = n - 1
		for j in range(n - 2, -1, -1):
			if arr[j] > arr[j + 1]:
				first_decr = j
			r[j] = first_decr
		ans = []
		for k in range(len(q)):
			left = q[k][0]
			right = q[k][1]
			if r[left] >= l[right]:
				ans.append('Yes')
			else:
				ans.append('No')
		return ans


class Solution:

	def processqueries(self, arr, n, m, q):
		left = [0] * n
		right = [0] * n
		left[0] = 0
		right[n - 1] = n - 1
		k = 0
		l = n - 1
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				k = i
			left[i] = k
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				l = i
			right[i] = l
		ans = []
		for i in range(m):
			if right[q[i][0]] >= left[q[i][1]]:
				ans.append('Yes')
			else:
				ans.append('No')
		return ans


class Solution:

	def processqueries(self, arr, n, m, q):
		right_arr = [n - 1]
		left_arr = [0]
		results = []
		left_ptr = 0
		right_ptr = n - 1
		for i in range(1, len(arr)):
			if arr[i] > arr[i - 1]:
				left_ptr = i
			left_arr.append(left_ptr)
		for i in range(len(arr) - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				right_ptr = i
			right_arr.append(right_ptr)
		right_arr.reverse()
		for tup in q:
			if right_arr[tup[0]] >= left_arr[tup[1]]:
				results.append('Yes')
			else:
				results.append('No')
		return results


class Solution:

	def preprocess(self, arr, N, left, right):
		left[0] = 0
		lastIncr = 0
		for i in range(1, N):
			if arr[i] > arr[i - 1]:
				lastIncr = i
			left[i] = lastIncr
		right[N - 1] = N - 1
		firstDecr = N - 1
		i = N - 2
		while i >= 0:
			if arr[i] > arr[i + 1]:
				firstDecr = i
			right[i] = firstDecr
			i -= 1

	def isSubarrayMountainForm(self, arr, left, right, L, R):
		return right[L] >= left[R]

	def processqueries(self, arr, n, m, q):
		result = []
		left = [0 for i in range(n)]
		right = [0 for i in range(n)]
		self.preprocess(arr, n, left, right)
		for i in q:
			(L, R) = i
			if self.isSubarrayMountainForm(arr, left, right, L, R):
				result.append('Yes')
			else:
				result.append('No')
		return result


class Solution:

	def processqueries(self, arr, n, m, q):
		return_array = []
		left = [0] * n
		right = [0] * n
		self.preprocess(arr, n, left, right)
		for j in range(m):
			if right[q[j][0]] >= left[q[j][1]]:
				return_array.append('Yes')
			else:
				return_array.append('No')
		return return_array

	def preprocess(self, arr, n, left, right):
		left[0] = 0
		lastIncr = 0
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				lastIncr = i
			left[i] = lastIncr
		right[n - 1] = n - 1
		firstDecr = n - 1
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				firstDecr = i
			right[i] = firstDecr


class Solution:

	def processqueries(self, arr, n, m, q):
		left = [0] * n
		left[0] = 0
		lastINCR = 0
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				lastINCR = i
			left[i] = lastINCR
		right = [0] * n
		firstDESC = n - 1
		right[n - 1] = firstDESC
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				firstDESC = i
			right[i] = firstDESC
		res = []
		for i in range(m):
			(rleft, rright) = q[i]
			if right[rleft] >= left[rright]:
				res.append('Yes')
			else:
				res.append('No')
		return res


class Solution:

	def processqueries(self, arr, n, m, q):
		left = [0] * n
		right = [0] * n
		self.mountainSubArray(left, right, n, arr)
		result = []
		for i in range(m):
			result.append(self.subArrayProcess(left, right, q[i]))
		return result

	def subArrayProcess(self, left, right, query):
		if right[query[0]] >= left[query[1]]:
			return 'Yes'
		else:
			return 'No'

	def mountainSubArray(self, left, right, n, arr):
		left[0] = 0
		right[n - 1] = n - 1
		lastIncr = 0
		firstDecr = n - 1
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				lastIncr = i
			left[i] = lastIncr
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				firstDecr = i
			right[i] = firstDecr
		return


class Solution:

	def processqueries(self, arr, n, m, q):
		ans = []
		left = [0] * n
		left[0] = 0
		lastIncr = 0
		right = [0] * n
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				lastIncr = i
			left[i] = lastIncr
		right[n - 1] = n - 1
		firstDecr = n - 1
		i = n - 2
		while i >= 0:
			if arr[i] > arr[i + 1]:
				firstDecr = i
			right[i] = firstDecr
			i -= 1
		for t in q:
			if right[t[0]] >= left[t[1]]:
				ans.append('Yes')
			else:
				ans.append('No')
		return ans


class Solution:

	def processqueries(self, arr, n, m, q):
		lastIncr = 0
		left = [0] * n
		left[0] = 0
		i = 1
		while i < n:
			if arr[i - 1] < arr[i]:
				lastIncr = i
			left[i] = lastIncr
			i += 1
		firstDecr = n - 1
		right = [0] * n
		right[n - 1] = n - 1
		i = n - 2
		while i >= 0:
			if arr[i] > arr[i + 1]:
				firstDecr = i
			right[i] = firstDecr
			i -= 1
		ret = []
		for p in q:
			(l, r) = (p[0], p[1])
			if right[l] >= left[r]:
				ret.append('Yes')
			else:
				ret.append('No')
		return ret


class Solution:

	def processqueries(self, arr, n, m, q):
		subarr = [-1] * m
		left = [-1] * n
		right = [-1] * n
		lastIncr = 0
		lastDecr = n - 1
		for i in range(n):
			if arr[i] > arr[i - 1]:
				lastIncr = i
			left[i] = lastIncr
		right[n - 1] = n - 1
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				lastDecr = i
			right[i] = lastDecr
		for (i, lr) in enumerate(q):
			l = lr[0]
			r = lr[1]
			subarr[i] = 'Yes' if right[l] >= left[r] else 'No'
		return subarr


class Solution:

	def processqueries(self, arr, n, m, q):
		left = [0 for i in range(n)]
		right = [0 for i in range(n)]
		left[0] = 0
		ptr = 0
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				ptr = i
			left[i] = ptr
		right[n - 1] = n - 1
		ptr = n - 1
		i = n - 2
		while i >= 0:
			if arr[i] > arr[i + 1]:
				ptr = i
			right[i] = ptr
			i -= 1
		ans = []
		for (i, j) in q:
			if left[j] <= right[i]:
				ans.append('Yes')
			else:
				ans.append('No')
		return ans


class Solution:

	def processqueries(self, arr, n, m, q):

		def brute_force(arr, n, m, q):

			def check_mountain(arr, start, end):
				maxx = -1
				(inc, dec) = (0, 0)
				while start < end:
					if arr[start] <= arr[start + 1]:
						inc = 1
						start += 1
					else:
						break
				while start < end:
					if arr[start] >= arr[start + 1]:
						dec = 1
						start += 1
					else:
						inc = 2
						break
				if inc == 2:
					return False
				return True
			result = []
			for query in q:
				if check_mountain(arr, query[0], query[1]):
					result.append('Yes')
				else:
					result.append('No')
			return result

		def optimized_preprocessing(arr, n, m, q):

			def preprocess(arr, n):
				(left, right) = ([0] * n, [0] * n)
				right[-1] = n - 1
				peak = 0
				for i in range(1, n):
					if arr[i] > arr[i - 1]:
						peak = i
					left[i] = peak
				peak = n - 1
				for i in range(n - 2, -1, -1):
					if arr[i] > arr[i + 1]:
						peak = i
					right[i] = peak
				return [left, right]
			(left, right) = preprocess(arr, n)
			result = []
			for query in q:
				if right[query[0]] >= left[query[1]]:
					result.append('Yes')
				else:
					result.append('No')
			return result
		return optimized_preprocessing(arr, n, m, q)
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		n = int(input())
		arr = list(map(int, input().split()))
		m = int(input())
		q = list()
		for i in range(0, m):
			q.append(list(map(int, input().split())))
		result = Solution().processqueries(arr, n, m, q)
		for i in result:
			print(i)


class Solution:

	def processqueries(self, arr, n, m, q):
		result = []
		left = [0] * n
		right = [0] * n
		left[0] = 0
		lastind = 0
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				lastind = i
			left[i] = lastind
		right[n - 1] = n - 1
		firstind = n - 1
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				firstind = i
			right[i] = firstind
		for i in range(m):
			if right[q[i][0]] >= left[q[i][1]]:
				result.append('Yes')
			else:
				result.append('No')
		return result
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		n = int(input())
		arr = list(map(int, input().split()))
		m = int(input())
		q = list()
		for i in range(0, m):
			q.append(list(map(int, input().split())))
		result = Solution().processqueries(arr, n, m, q)
		for i in result:
			print(i)


class Solution:

	def processqueries(self, arr, n, m, q):
		res = []
		left = [0 for i in range(n)]
		right = [0 for i in range(n)]
		left[0] = 0
		lastptr = 0
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				lastptr = i
			left[i] = lastptr
		right[n - 1] = n - 1
		lastptr = n - 1
		i = n - 2
		while i >= 0:
			if arr[i] > arr[i + 1]:
				lastptr = i
			right[i] = lastptr
			i -= 1
		for i in range(0, m):
			(l, r) = (q[i][0], q[i][1])
			if right[l] >= left[r]:
				res.append('Yes')
			else:
				res.append('No')
		return res


class Solution:

	def processqueries(self, a, n, m, q):
		left = [0] * n
		prev = 0
		for i in range(1, n):
			if a[i] > a[i - 1]:
				prev = i
			left[i] = prev
		right = [0] * n
		right[n - 1] = n - 1
		prevd = n - 1
		for i in range(n - 2, -1, -1):
			if a[i] > a[i + 1]:
				prevd = i
			right[i] = prevd
		ans = []
		for i in q:
			(l, r) = i
			if right[l] >= left[r]:
				ans.append('Yes')
			else:
				ans.append('No')
		return ans


class Solution:

	def util(self, arr, left, right):
		left[0] = 0
		pointer = 0
		for i in range(1, len(arr)):
			if arr[i] > arr[i - 1]:
				pointer = i
			left[i] = pointer
		right[len(arr) - 1] = len(arr) - 1
		pointer = len(arr) - 1
		for i in range(len(arr) - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				pointer = i
			right[i] = pointer

	def truth(self, left, right, L, R):
		return right[L] >= left[R]

	def processqueries(self, arr, n, m, q):
		res = []
		left = [0] * len(arr)
		right = [0] * len(arr)
		self.util(arr, left, right)
		for element in q:
			L = element[0]
			R = element[1]
			if self.truth(left, right, L, R):
				res.append('Yes')
			else:
				res.append('No')
		return res


class Solution:

	def processqueries(self, arr, n, m, q):
		left = [0] * n
		right = [n - 1] * n
		temp = 0
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				temp = i
			left[i] = temp
		temp = n - 1
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				temp = i
			right[i] = temp
		ans = ['No'] * m
		for i in range(m):
			l = q[i][0]
			r = q[i][1]
			if right[l] >= left[r]:
				ans[i] = 'Yes'
		return ans


class Solution:

	def processqueries(self, arr, n, m, q):
		l = [0] * n
		r = [0] * n
		l[0] = 0
		last_incr = 0
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				last_incr = i
			l[i] = last_incr
		r[n - 1] = n - 1
		first_decr = n - 1
		for j in range(n - 2, -1, -1):
			if arr[j] > arr[j + 1]:
				first_decr = j
			r[j] = first_decr
		ans = []
		for i in range(m):
			le = q[i][0]
			ri = q[i][1]
			if r[le] >= l[ri]:
				ans.append('Yes')
			else:
				ans.append('No')
		return ans


class Solution:

	def processqueries(self, arr, n, m, q):
		l = [-1] * n
		r = [-1] * n
		l[0] = 0
		lastInc = 0
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				lastInc = i
			l[i] = lastInc
		r[n - 1] = n - 1
		firstDec = n - 1
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				firstDec = i
			r[i] = firstDec
		ans = []
		for i in range(m):
			left = q[i][0]
			rig = q[i][1]
			if r[left] >= l[rig]:
				ans.append('Yes')
			else:
				ans.append('No')
		return ans


class Solution:

	def processqueries(self, arr, n, m, q):
		left = [0] * n
		right = [0] * n
		last_incr = 0
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				last_incr = i
			left[i] = last_incr
		right[n - 1] = n - 1
		first_decr = n - 1
		for j in range(n - 2, -1, -1):
			if arr[j] > arr[j + 1]:
				first_decr = j
			right[j] = first_decr
		ans = []
		for i in range(m):
			L = q[i][0]
			R = q[i][1]
			if right[L] >= left[R]:
				ans.append('Yes')
			else:
				ans.append('No')
		return ans


class Solution:

	def processqueries(self, arr, n, m, q):
		left = [0 for i in range(n)]
		left[0] = 0
		lastinc = 0
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				lastinc = i
			left[i] = lastinc
		right = [0 for i in range(n)]
		right[n - 1] = n - 1
		lastdec = n - 1
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				lastdec = i
			right[i] = lastdec
		res = []
		for qry in q:
			res.append('Yes' if right[qry[0]] >= left[qry[1]] else 'No')
		return res


class Solution:

	def preprocess(self, arr, n, left, right):
		left[0] = 0
		lastoccr = 0
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				lastoccr = i
			left[i] = lastoccr
		right[n - 1] = n - 1
		i = n - 2
		lastoccr = n - 1
		while i >= 0:
			if arr[i] > arr[i + 1]:
				lastoccr = i
			right[i] = lastoccr
			i -= 1
		return (left, right)

	def checkmountain(self, left, right, l, r):
		return right[l] >= left[r]

	def processqueries(self, arr, n, m, q):
		left = [0 for i in range(n)]
		right = [0 for i in range(n)]
		(left, right) = self.preprocess(arr, n, left, right)
		answer = []
		for element in q:
			(l, r) = element
			if self.checkmountain(left, right, l, r):
				answer.append('Yes')
			else:
				answer.append('No')
		return answer


class Solution:

	def processqueries(self, arr, n, m, q):
		leftToRight = [0 for _ in range(n)]
		rightToLeft = [n - 1 for _ in range(n)]
		lpointer = 0
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				lpointer = i
			leftToRight[i] = lpointer
		rpointer = n - 1
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				rpointer = i
			rightToLeft[i] = rpointer
		res = []
		for (start, end) in q:
			res.append('Yes' if rightToLeft[start] >= leftToRight[end] else 'No')
		return res


class Solution:

	def processqueries(self, arr, n, m, q):
		left_ = [0] * n
		ptr = 0
		for i in range(1, n):
			if arr[i - 1] < arr[i]:
				ptr = i
			left_[i] = ptr
		right_ = [0] * n
		right_[n - 1] = n - 1
		ptr = n - 1
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				ptr = i
			right_[i] = ptr
		res = []
		for _ in range(m):
			(L, R) = q.pop(0)
			if right_[L] >= left_[R]:
				res.append('Yes')
			else:
				res.append('No')
		return res


class Solution:

	def processqueries(self, arr, n, m, q):
		result = []
		left = [0] * n
		right = [0] * n
		self.preProcess(left, right, arr, n)
		for i in q:
			(s, e) = i
			if self.haveMountain(s, e, left, right):
				result.append('Yes')
			else:
				result.append('No')
		return result

	def preProcess(self, left, right, arr, n):
		lastIncr = 0
		left[0] = lastIncr
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				lastIncr = i
			left[i] = lastIncr
		firstDecr = n - 1
		right[n - 1] = firstDecr
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				firstDecr = i
			right[i] = firstDecr

	def haveMountain(self, s, e, left, right):
		return right[s] >= left[e]


class Solution:

	def processqueries(self, arr, n, m, q):
		res = []
		left = [0 for i in range(n)]
		right = [0 for j in range(n)]
		left[0] = 0
		lastInc = 0
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				lastInc = i
			left[i] = lastInc
		right[n - 1] = n - 1
		firDec = n - 1
		i = n - 2
		while i >= 0:
			if arr[i] > arr[i + 1]:
				firDec = i
			right[i] = firDec
			i -= 1
		for i in range(m):
			if IsSubArr(left, right, q[i][0], q[i][1]):
				res.append('Yes')
			else:
				res.append('No')
		return res

def IsSubArr(left, right, L, R):
	return right[L] >= left[R]


class Solution:

	def processqueries(self, arr, n, m, q):
		left = [0] * n
		right = [0] * n
		right[n - 1] = n - 1
		last = 0
		for i in range(1, n):
			if arr[i - 1] < arr[i]:
				last = i
			left[i] = last
		last = n - 1
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				last = i
			right[i] = last
		op = []
		for (i, j) in q:
			op.append('Yes' if right[i] >= left[j] else 'No')
		return op


class Solution:

	def processqueries(self, arr, n, m, q):
		res = ['No'] * m
		left = [0] * n
		right = [n - 1] * n
		temp = []
		for i in range(n - 1, 0, -1):
			temp.append(i)
			while temp and arr[i - 1] < arr[i]:
				left[temp[-1]] = i
				temp.pop()
		temp = []
		for i in range(0, n - 1):
			temp.append(i)
			while temp and arr[i] > arr[i + 1]:
				right[temp[-1]] = i
				temp.pop()
		for query in range(m):
			l = q[query][0]
			r = q[query][1]
			if right[l] >= left[r]:
				res[query] = 'Yes'
		return res


class Solution:

	def processqueries(self, arr, n, m, q):
		incr = [-1] * n
		decr = [-1] * n
		lastInc = 0
		incr[0] = 0
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				lastInc = i
			incr[i] = lastInc
		firstDec = n - 1
		decr[n - 1] = n - 1
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				firstDec = i
			decr[i] = firstDec
		res = []
		for query in q:
			s = query[0]
			e = query[1]
			if decr[s] >= incr[e]:
				res.append('Yes')
			else:
				res.append('No')
		return res


class Solution:

	def processqueries(self, arr, n, m, q):
		max = n - 1
		min = 0
		res = []
		smaller = [0] * n
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				min = i
			smaller[i] = min
		greater = [0] * n
		greater[n - 1] = n - 1
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				max = i
			greater[i] = max
		for i in range(m):
			l = q[i][0]
			r = q[i][1]
			if greater[l] >= smaller[r]:
				res.append('Yes')
			else:
				res.append('No')
		return res


class Solution:

	def processqueries(self, arr, n, m, q):
		next_dec_index = n - 1
		next_dec_indices = [next_dec_index for _ in range(n)]
		prev_inc_index = 0
		prev_inc_indices = [prev_inc_index for _ in range(n)]
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				next_dec_index = i
			next_dec_indices[i] = next_dec_index
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				prev_inc_index = i
			prev_inc_indices[i] = prev_inc_index
		result = []
		for query in q:
			left_bound = query[0]
			right_bound = query[1]
			if prev_inc_indices[right_bound] <= next_dec_indices[left_bound]:
				result.append('Yes')
			else:
				result.append('No')
		return result


class Solution:

	def processqueries(self, arr, n, m, q):
		lastIncreased = [0] * n
		lastDecreased = [0] * n
		li = 0
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				li = i
			lastIncreased[i] = li
		ld = n - 1
		lastDecreased[-1] = n - 1
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				ld = i
			lastDecreased[i] = ld
		res = []
		for query in q:
			(s, e) = query
			if lastDecreased[s] >= lastIncreased[e]:
				ans = 'Yes'
			else:
				ans = 'No'
			res.append(ans)
		return res


from collections import deque

class Solution:

	def processqueries(self, arr, n, m, q):
		left = []
		right = deque()
		left.append(0)
		right.append(n - 1)
		ind = 0
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				ind = i
			left.append(ind)
		ind = n - 1
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				ind = i
			right.appendleft(ind)
		ans = []
		for i in range(len(q)):
			if right[q[i][0]] >= left[q[i][1]]:
				ans.append('Yes')
			else:
				ans.append('No')
		return ans


class Solution:

	def processqueries(self, arr, n, m, q):
		left = [0] * n
		right = [0] * n
		lin = 0
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				lin = i
			left[i] = lin
		right[n - 1] = n - 1
		rd = n - 1
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				rd = i
			right[i] = rd
		out = []
		for i in range(m):
			l = q[i][0]
			r = q[i][1]
			if right[l] >= left[r]:
				out.append('Yes')
				continue
			out.append('No')
		return out


class Solution:

	def preprocess(self, arr, left, right):
		n = len(arr)
		left[0] = 0
		leftInd = 0
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				leftInd = i
			left[i] = leftInd
		right[n - 1] = n - 1
		rightInd = n - 1
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				rightInd = i
			right[i] = rightInd

	def isMountain(self, arr, L, R, left, right):
		return right[L] >= left[R]

	def processqueries(self, arr, n, m, q):
		returnArr = []
		left = [0 for _ in range(n)]
		right = [0 for _ in range(n)]
		self.preprocess(arr, left, right)
		for i in q:
			isM = self.isMountain(arr, i[0], i[1], left, right)
			returnArr.append('Yes' if isM else 'No')
		return returnArr


class Solution:

	def processqueries(self, arr, n, m, q):
		l = len(arr)
		left = [0] * l
		right = [0] * l
		right[l - 1] = l - 1
		i = 1
		lastptr = 0
		while i < l:
			if arr[i] > arr[i - 1]:
				lastptr = i
			left[i] = lastptr
			i += 1
		i = l - 2
		while i >= 0:
			if arr[i] > arr[i + 1]:
				lastptr = i
			right[i] = lastptr
			i -= 1
		res = []
		for (a, b) in q:
			if right[a] >= left[b]:
				res.append('Yes')
			else:
				res.append('No')
		return res


class Solution:

	def processqueries(self, arr, n, m, q):
		left = [0] * n
		right = [0] * n
		left[0] = 0
		lastincr = 0
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				lastincr = i
			left[i] = lastincr
		right[n - 1] = n - 1
		lastdecr = n - 1
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				lastdecr = i
			right[i] = lastdecr
		list = []
		for query in q:
			if right[query[0]] >= left[query[1]]:
				list.append('Yes')
			else:
				list.append('No')
		return list


class Solution:

	def processqueries(self, arr: list, n: int, m: int, q: list) -> list:
		ans = []
		left = [0] * n
		leftIncrPtr = 0
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				leftIncrPtr = i
			left[i] = leftIncrPtr
		right = [0] * n
		right[n - 1] = n - 1
		rightDecrPtr = n - 1
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				rightDecrPtr = i
			right[i] = rightDecrPtr
		for query in q:
			(l, r) = query
			if right[l] >= left[r]:
				ans.append('Yes')
			else:
				ans.append('No')
		return ans


class Solution:

	def processqueries(self, arr, n, m, q):
		l_arr = [0] * n
		l_inc = 0
		r_arr = [0] * n
		r_arr[n - 1] = n - 1
		r_incr = n - 1
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				l_inc = i
			l_arr[i] = l_inc
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				r_incr = i
			r_arr[i] = r_incr
		result = []
		for ele in q:
			(l, r) = (ele[0], ele[1])
			if r_arr[l] >= l_arr[r]:
				result.append('Yes')
			else:
				result.append('No')
		return result


class Solution:

	def processqueries(self, arr, n, m, q):
		left = [0] * n
		lastIncr = 0
		for ind in range(1, n):
			if arr[ind] > arr[ind - 1]:
				lastIncr = ind
			left[ind] = lastIncr
		right = [n - 1] * n
		firstDec = n - 1
		for ind in range(n - 2, -1, -1):
			if arr[ind] > arr[ind + 1]:
				firstDec = ind
			right[ind] = firstDec
		res = []
		for query in q:
			(l, r) = query
			if self.ifmountain(arr, left, right, l, r):
				res.append('Yes')
			else:
				res.append('No')
		return res

	def ifmountain(self, arr, left, right, l, r):
		return right[l] >= left[r]


class Solution:

	def processqueries(self, arr, n, m, q):

		def preprocess(arr, n):
			left = [0] * n
			lastptr = 0
			for i in range(1, n):
				if arr[i] > arr[i - 1]:
					lastptr = i
				left[i] = lastptr
			right = [0] * n
			right[-1] = n - 1
			lastptr = n - 1
			for i in range(n - 2, -1, -1):
				if arr[i] > arr[i + 1]:
					lastptr = i
				right[i] = lastptr
			return (left, right)
		(left, right) = preprocess(arr, n)
		results = []
		for r in range(m):
			if right[q[r][0]] >= left[q[r][1]]:
				results.append('Yes')
			else:
				results.append('No')
		return results


class Solution:

	def processqueries(self, arr, n, m, q):
		(left, right) = self._analize_decreasing(arr)
		result = []
		for query in q:
			if right[query[0]] >= left[query[1]]:
				result.append('Yes')
			else:
				result.append('No')
		return result

	def _analize_decreasing(self, arr):
		left = [None] * len(arr)
		left[0] = 0
		last_increase = 0
		for i in range(1, len(arr)):
			if arr[i] > arr[i - 1]:
				last_increase = i
			left[i] = last_increase
		right = [None] * len(arr)
		right[len(arr) - 1] = len(arr) - 1
		last_decrease = len(arr) - 1
		for i in range(len(arr) - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				last_decrease = i
			right[i] = last_decrease
		return (left, right)

	def _analize_query_3(self, arr, query, result):
		to_query = arr[query[0]:query[1] + 1]
		if len(to_query) == 1:
			result.append('Yes')
			return
		max_index = 0
		for i in range(1, len(to_query)):
			if to_query[i] > to_query[max_index]:
				max_index = i
		left = to_query[:max_index + 1]
		right = to_query[max_index:]
		for i in range(len(left) - 1):
			if not left[i] <= left[i + 1]:
				result.append('No')
				return
		for i in range(1, len(right) - 1):
			if not right[i] >= right[i + 1]:
				result.append('No')
				return
		result.append('Yes')
		return

	def _analize_query_2(self, arr, query, result):
		to_query = arr[query[0]:query[1] + 1]
		if len(to_query) == 1:
			result.append('Yes')
			return
		max_index = 0
		for i in range(1, len(to_query)):
			if to_query[i] > to_query[max_index]:
				max_index = i
		if max_index != 0:
			for i in range(0, max_index - 1):
				if not to_query[i] <= to_query[i + 1] <= to_query[max_index]:
					result.append('No')
					return
		for i in range(len(to_query) - 1, max_index, -1):
			if not to_query[i] <= to_query[i - 1] <= to_query[max_index]:
				result.append('No')
				return
		result.append('Yes')
		return


class Solution:

	def preprocess(self, arr, N, left, right):
		left[0] = 0
		lastIncr = 0
		for i in range(1, N):
			if arr[i] > arr[i - 1]:
				lastIncr = i
			left[i] = lastIncr
		right[N - 1] = N - 1
		firstDecr = N - 1
		i = N - 2
		while i >= 0:
			if arr[i] > arr[i + 1]:
				firstDecr = i
			right[i] = firstDecr
			i -= 1

	def is_mountain(self, arr, left_arr, right_arr, L, R):
		return right_arr[L] >= left_arr[R]

	def processqueries(self, arr, n, m, q):
		result = []
		valid = True
		left_arr = [0 for i in range(n)]
		right_arr = [0 for i in range(n)]
		self.preprocess(arr, n, left_arr, right_arr)
		for query in q:
			L = query[0]
			R = query[1]
			if self.is_mountain(arr, left_arr, right_arr, L, R):
				result.append('Yes')
			else:
				result.append('No')
		return result


class Solution:

	def processqueries(self, arr, n, m, q):
		(leftinc, rightinc) = (0, n - 1)
		(left, right) = ([0] * n, [0] * n)
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				leftinc = i
			left[i] = leftinc
		right[n - 1] = n - 1
		for i in reversed(range(n - 1)):
			if arr[i] > arr[i + 1]:
				rightinc = i
			right[i] = rightinc
		val = []
		for i in range(m):
			if right[q[i][0]] >= left[q[i][1]]:
				val.append('Yes')
			else:
				val.append('No')
		return val