In a country Stone Land, there are $N$ stones arranged in a row from left to right. Each stone has some height represented by a positive number. The stones are numbered from $1$ to $N$ from left to right.

You are given an array H of size $N$ consisting of the height of the $N$ stones from left to
right.

Stone at $j^{th}$ position is visible from the stone at $i^{th}$ position if:-
1. $j>i$
2. $max(H[i],H[i+1],H[i+2],....,H[j-1])$ $<$ $H[j]$

You are asked $M$ queries.
Each query consists of two different positions of stones $A$ and $B$.
You have to Print the total number of stones that are visible from both the stones at the position $A$ and $B$.

------  Input ------

The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $M$, where $N$ is the number of stones and $M$ is the number of queries.
The Second line consists of $N$ space-separated integers (array H) denoting the height of stones from left to the right separated by a space.
Next, $M$ lines consist of two space-separated integers $A$ and $B$ separated by space where $A$ and $B$ are positions of stones.

------  Constraints ------
$1 ≤ T ≤ 5$
$2 ≤ N ≤ 10^{5}$
$1 ≤ M ≤ 10^{5}$
$1 ≤ H[i] ≤ 10^{9}$, where H[i] denotes the height of $i^{th}$ stone, and $1 ≤ i ≤ N$
$1 ≤ A, B ≤ N$
It is guaranteed that the sum of $N$ over all test cases does not exceed $10^{5}$.
It is guaranteed that the sum of $M$ over all test cases does not exceed $10^{5}$.

------  Output ------
For each query, print the total number of stones that are visible from both the stones at the position $A$ and $B$ in a new line.

------  Example Input ------

1
6 6
3 10 20 20 5 50
1 2
2 4
4 3
4 5
1 3
4 4

------  Example Output ------

2
1
1
1
1
1

------  Explanation ------

Query $1$: Stone at position $1$ can see the stones at position $(2, 3, 6)$ whereas stone at position $2$ can see the stones at position $(3, 6)$. Thus, the total number of stones that are visible from both stones is $2$.

Source: codechef | Difficulty: VERY_HARD
Tags: Data structures

Range queries

Segment trees revisited


Solutions:
from sys import stdin, stdout
input = stdin.readline

class SegmentTree:

	def __init__(self, data, default=[-float('inf'), -1], func=max):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		start += self._size
		stop += self._size + 1
		res_left = res_right = self._default
		while start < stop:
			if start & 1:
				res_left = self._func(res_left, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res_right = self._func(self.data[stop], res_right)
			start >>= 1
			stop >>= 1
		return self._func(res_left, res_right)

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	ST = SegmentTree([[arr[i], i] for i in range(n)])
	vals = [0 for i in range(n)]
	st = []
	for i in range(n - 1, -1, -1):
		while st and arr[st[-1]] <= arr[i]:
			st.pop()
		if st:
			vals[i] = 1 + vals[st[-1]]
		st.append(i)
	for i in range(q):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		(a, b) = (min(a, b), max(a, b))
		print(vals[ST.query(a, b)[1]])


from math import log2

def pre():
	s = []
	for i in range(n):
		if len(s) == 0:
			s.append(i)
			continue
		while len(s) and a[s[-1]] < a[i]:
			nm[s[-1]] = i
			s.pop()
		s.append(i)
	for i in range(n - 1, -1, -1):
		if nm[i] != -1:
			ans[i] = ans[nm[i]] + 1

def sparsetable():
	for i in range(n):
		s[i][0] = [a[i], i]
	for i in range(1, len(s[0])):
		for j in range(n - (1 << i) + 1):
			s[j][i] = s[j][i - 1][:]
			if s[j][i][0] < s[j + (1 << i - 1)][i - 1][0]:
				s[j][i] = s[j + (1 << i - 1)][i - 1][:]

def query(x, y):
	v = y - x + 1
	(m, ind) = (0, -1)
	for i in range(len(s[0]), -1, -1):
		if v >> i & 1:
			if m < s[x][i][0]:
				m = s[x][i][0]
				ind = s[x][i][1]
			x += 1 << i
	return ans[ind]
for T in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = [0] * (n + 1)
	nm = [-1] * n
	s = [[[0, 0] for i in range(int(log2(n)) + 1)] for j in range(n)]
	pre()
	sparsetable()
	for i in range(q):
		(x, y) = map(int, input().split())
		print(query(min(x, y) - 1, max(x, y) - 1))


segment_tree = []
height = []

def build(ind, start, end):
	if start == end:
		segment_tree[ind] = (height[start], start)
		return segment_tree[ind]
	mid = (start + end) // 2
	left = build(2 * ind + 1, start, mid)
	right = build(2 * ind + 2, mid + 1, end)
	if left[0] > right[0]:
		segment_tree[ind] = left
	else:
		segment_tree[ind] = right
	return segment_tree[ind]

def query(ind, start, end, l, r):
	if start > r or end < l:
		return (-float('inf'), -1)
	if l <= start and r >= end:
		return segment_tree[ind]
	mid = (start + end) // 2
	left = query(2 * ind + 1, start, mid, l, r)
	right = query(2 * ind + 2, mid + 1, end, l, r)
	if left[0] > right[0]:
		return left
	else:
		return right
t = int(input())
for _ in range(t):
	(n_stones, m_queries) = map(int, input().split())
	segment_tree = [0] * (n_stones * 4)
	height = list(map(int, input().split()))
	build(0, 0, n_stones - 1)
	stack = []
	for i in range(n_stones - 1, -1, -1):
		curr = height[i]
		while stack and stack[-1] <= curr:
			stack.pop(-1)
		height[i] = len(stack)
		stack.append(curr)
	for _ in range(m_queries):
		(l, r) = map(int, input().split())
		if l > r:
			(l, r) = (r, l)
		l -= 1
		r -= 1
		(_, ind) = query(0, 0, n_stones - 1, l, r)
		print(height[ind])


import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)
from queue import PriorityQueue
from math import gcd
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
level = 20

def edge(u, v):
	tree[u].append(v)
	tree[v].append(u)

def dfs(u, p):
	depth[u] = depth[p] + 1
	parent[u][0] = p
	for i in tree[u]:
		if i == p:
			continue
		dfs(i, u)

def pre(n):
	for i in range(1, level):
		for j in range(1, n + 1):
			if parent[j][i - 1] != -1:
				parent[j][i] = parent[parent[j][i - 1]][i - 1]

def lca(u, v):
	if depth[v] < depth[u]:
		(u, v) = (v, u)
	diff = depth[v] - depth[u]
	for i in range(level):
		if diff >> i & 1:
			v = parent[v][i]
	if u == v:
		return u
	for i in range(level - 1, -1, -1):
		if parent[u][i] != parent[v][i]:
			u = parent[u][i]
			v = parent[v][i]
	return parent[u][0]
for _ in range(ii()):
	(n, m) = il()
	a = il() + [float('inf')]
	nxt = [-1 for i in range(n + 1)]
	dp = [0 for i in range(n + 1)]
	depth = [0 for i in range(n + 2)]
	tree = [[] for i in range(n + 2)]
	parent = [[0 for i in range(level)] for i in range(n + 2)]
	b = []
	t = 0
	for i in range(n + 1):
		while t != 0 and a[b[-1]] < a[i]:
			nxt[b[-1]] = i
			b.pop()
			t -= 1
		b.append(i)
		t += 1
	for i in range(n - 1, -1, -1):
		if nxt[i] == -1:
			continue
		edge(i + 1, nxt[i] + 1)
		dp[i] = dp[nxt[i]] + 1
	depth[n] = 0
	dfs(n + 1, 0)
	pre(n + 1)
	for i in range(m):
		(u, v) = il()
		l = lca(u, v)
		l -= 1
		if l == u - 1 or l == v - 1:
			print(max(0, dp[l] - 1))
		else:
			print(dp[l])


import sys
sys.setrecursionlimit(100000 + 10)
for _ in range(int(input())):

	def build(a, ind, low, high):
		if low == high:
			st[ind] = [a[low], low]
			return st[ind]
		else:
			mid = low + (high - low) // 2
			left = build(a, 2 * ind + 1, low, mid)
			right = build(a, 2 * ind + 2, mid + 1, high)
			st[ind] = left[:] if left[0] > right[0] else right[:]
			return st[ind]

	def query(ind, low, high, l, r):
		if low > r or high < l:
			return [float('-inf'), -1]
		if l <= low and r >= high:
			return st[ind]
		mid = low + (high - low) // 2
		left = query(2 * ind + 1, low, mid, l, r)
		right = query(2 * ind + 2, mid + 1, high, l, r)
		return left if left[0] > right[0] else right
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	st = [0 for i in range(4 * n)]
	build(a, 0, 0, n - 1)
	(stack, ans) = ([], [-1] * n)
	res = [0] * n
	for i in range(n):
		while stack and a[stack[-1]] < a[i]:
			ans[stack.pop()] = i
		stack.append(i)
	for i in range(n - 1, -1, -1):
		if ans[i] != -1:
			res[i] = 1 + res[ans[i]]
	for i in range(m):
		(l, r) = map(int, input().split())
		if l > r:
			(l, r) = (r, l)
		l -= 1
		r -= 1
		(ele, ind) = query(0, 0, n - 1, l, r)
		print(res[ind])


import sys, os
from io import BytesIO, IOBase
mod = 10 ** 9 + 7
Mod = 998244353
INF = float('inf')
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
sys.setrecursionlimit(100000 + 10)
tc = 1
tc = int(input())
for test in range(1, tc + 1):
	(n, m) = inp()
	a = inp()
	st = [float('inf') for i in range(4 * len(a))]

	def build(a, ind, start, end):
		if start == end:
			st[ind] = [a[start], start]
		else:
			mid = (start + end) // 2
			build(a, 2 * ind + 1, start, mid)
			build(a, 2 * ind + 2, mid + 1, end)
			A = st[2 * ind + 1]
			B = st[2 * ind + 2]
			if A[0] > B[0]:
				st[ind] = A.copy()
			else:
				st[ind] = B.copy()
			return st[ind]
	build(a, 0, 0, n - 1)

	def query(ind, l, r, start, end):
		if start > r or end < l:
			return [float('-inf'), -1]
		if l <= start <= end <= r:
			return st[ind]
		mid = (start + end) // 2
		A = query(2 * ind + 1, l, r, start, mid)
		B = query(2 * ind + 2, l, r, mid + 1, end)
		if A[0] > B[0]:
			return A
		return B
	ans = [-1] * n
	stack = []
	for i in range(n):
		while stack and a[stack[-1]] < a[i]:
			ans[stack.pop()] = i
		stack.append(i)
	res = [0] * n
	for i in range(n - 1, -1, -1):
		if ans[i] != -1:
			res[i] = 1 + res[ans[i]]
	for i in range(m):
		(l, r) = inp()
		if l > r:
			(l, r) = (r, l)
		l -= 1
		r -= 1
		(lol, ind) = query(0, l, r, 0, n - 1)
		print(res[ind])


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop
import math
from collections import *
from functools import reduce, cmp_to_key, lru_cache
import sys
input = sys.stdin.readline
M = mod = 998244353

def factors(n):
	return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip('\n').split()]

def st():
	return input().rstrip('\n')

def val():
	return int(input().rstrip('\n'))

def li2():
	return [i for i in input().rstrip('\n')]

def li3():
	return [int(i) for i in input().rstrip('\n')]

def compress(l):
	ind = 1
	s = set(l)
	index = defaultdict(list)
	for i in range(n):
		index[l[i]].append(i)
	for i in sorted(s):
		for j in index[i]:
			l[j] = ind
		ind += 1
	return l[:]

class Node:

	def __init__(self, s, e):
		self.start = s
		self.end = e
		self.val = 0
		self.left = None
		self.right = None

def build(nums, l, r):
	if l == r:
		temp = Node(l, l)
		temp.val = nums[l]
	else:
		mid = l + r >> 1
		temp = Node(l, r)
		temp.left = build(nums, l, mid)
		temp.right = build(nums, mid + 1, r)
		temp.val = max(temp.left.val, temp.right.val)
	return temp

def update(root, start, value):
	if root.start == start == root.end:
		root.val = value
	elif root.start <= start and root.end >= start:
		update(root.left, start, value)
		update(root.right, start, value)
		root.val = max(root.left.val, root.right.val)

def query(root, start, end):
	if root.start >= start and root.end <= end:
		return root.val
	elif root.start > end or root.end < start:
		return -float('inf')
	else:
		temp1 = query(root.left, start, end)
		temp2 = query(root.right, start, end)
		return max(temp1, temp2)

class Bitree:

	def __init__(self):
		self.bitree = []

	def getsum(self, i):
		s = 0
		i += 1
		while i > 0:
			s += self.bitree[i]
			i -= i & -i
		return s

	def sum(self, a, b):
		return self.getsum(b) - self.getsum(a - 1) if a else self.getsum(b)

	def update(self, i, v):
		i += 1
		while i < len(self.bitree):
			self.bitree[i] += v
			i += i & -i

	def build(self, arr):
		n = len(arr)
		self.bitree = [0] * (n + 1)
		for i in range(n):
			self.update(i, arr[i])
for _ in range(val()):
	(n, m) = li()
	l = compress(li())
	root = build(l, 0, n - 1)
	queries = defaultdict(list)
	ans = [0] * m
	for i in range(m):
		(x, y) = sorted(li())
		queries[y].append([x, i])
	for i in queries:
		queries[i] = sorted(queries[i])
	fenwick = Bitree()
	fenwick.build([0] * (n + 10))
	stack = deque()
	for i in range(n - 1, -1, -1):
		while stack and stack[0] <= l[i]:
			fenwick.update(stack[0], -1)
			stack.popleft()
		for (j, ind) in queries[i + 1]:
			ma = query(root, j - 1, i)
			ans[ind] = fenwick.sum(ma + 1, n + 3)
		stack.appendleft(l[i])
		fenwick.update(l[i], 1)
	for i in ans:
		print(i)