Tsetso likes to play with arrays. 

An Array A[1,2,\ldots,N] is said to be a Tsetso array if A[1] \cdot A[N] = max(A_{1},A_{2},\ldots,A_{N-1},A_{N}).

Bedo, his teammate, likes to solve problems so much, so Tsetso gave him an array A of N \bf{distinct} integers A_{1}, A_{2}, \ldots, A_{N} and Q queries of the form [L, R] and asked him to count the number of Tsetso subarrays in the given range.

A subarray[L,R] is to be a Tsetso subarray if A[L] \cdot A[R] = max(A_{L},A_{L+1},....,A_{R-1},A_{R}).

Bedo spent a lot of time trying to solve it, but he couldn't, can you?

\bf{Note}: A sequence a is a subarray of a sequence b if a can be obtained from b by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. 

------ Input Format ------ 

- First-line will contain T, the number of test cases. Then the test cases follow.
- The first line of input contains two space-separated integers N and Q, the number of elements in the array, and the number of queries.
- The second line contains N \bf{distinct} space-separated integers A_{1}, A_{2}, \ldots, A_{N}.
- Then Q lines follow each line containing two space-separated integers L, R. 

------ Output Format ------ 

For each query, output in a single line the number of Tsetso subarrays in the given range [L, R].

------ Constraints ------ 

$1 ≤ T ≤ 10$
$2 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{18} $
$1 ≤ Q ≤ 5 \cdot 10^{5}$
$1 ≤L ≤R ≤N$
- Sum of $N$ over all testcases is atmost $10^{5}$.
- Sum of $Q$ over all testcases is atmost $5 \cdot 10^{5}$.

----- Sample Input 1 ------ 
1
7 3
3 6 24 4 1 8 2
1 7
2 5
4 7
----- Sample Output 1 ------ 
7
4
4
----- explanation 1 ------ 
- All the valid subarrays are $[1,6],[2,4],[3,5],[4,5],[5,5],[5,6],[4,7]$.
- One of the invalid subarrays is $[1,3] , 3 \cdot 24 \neq max(3,6,24) $

Source: codechef | Difficulty: VERY_HARD
Tags: Sorting

Range queries

Complete search

Segment trees revisited

Number theory

Mathematics

Data structures


Solutions:
mod = 10 ** 9 + 7

def update(i, val):
	while i < len(bit):
		bit[i] += val
		i += i & -i

def get(i):
	ans = 0
	while i:
		ans += bit[i]
		i -= i & -i
	return ans
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	que = []
	d = {}
	(lft, rig, s, s1) = ([], [], [], [])
	for i in range(q):
		(l, r) = map(int, input().split())
		que.append([r, -l, i])
	for i in range(n):
		d[a[i]] = i
	for i in range(n):
		while len(s) and a[s[-1]] < a[i]:
			s.pop()
		lft.append(-1 if len(s) == 0 else s[-1])
		s.append(i)
	for i in reversed(range(n)):
		while len(s1) and a[s1[-1]] < a[i]:
			s1.pop()
		rig.append(n if len(s1) == 0 else s1[-1])
		s1.append(i)
	rig = rig[::-1]
	for i in range(n):
		l = lft[i] + 1
		r = rig[i] - 1
		if i - l < r - i:
			for j in range(l, i + 1):
				if a[i] % a[j]:
					continue
				y = a[i] // a[j]
				if d.get(y) is None:
					continue
				z = d[y]
				if z < i or z > r:
					continue
				que.append([z + 1, -j - 1, -1])
		else:
			for j in range(i, r + 1):
				if a[i] % a[j] != 0:
					continue
				y = a[i] // a[j]
				if d.get(y) is None:
					continue
				z = d[y]
				if z > i or z < l:
					continue
				que.append([j + 1, -z - 1, -1])
	que.sort()
	ans = [0 for i in range(q)]
	bit = [0 for i in range(n + 2)]
	for i in range(len(que)):
		(l, r) = (-que[i][1], que[i][0])
		x = que[i][2]
		if x == -1:
			update(l, 1)
		else:
			ans[x] = get(r) - get(l - 1)
	for i in ans:
		print(i)


from bisect import bisect_right as lb
from collections import deque
from queue import PriorityQueue as pq
from math import gcd
mod = 10 ** 9 + 7

def update(i, val):
	while i < len(bit):
		bit[i] += val
		i += i & -i

def get(i):
	ans = 0
	while i:
		ans += bit[i]
		i -= i & -i
	return ans
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	que = []
	d = {}
	(lft, rig, s, s1) = ([], [], [], [])
	for i in range(q):
		(l, r) = map(int, input().split())
		que.append([r, -l, i])
	for i in range(n):
		d[a[i]] = i
	for i in range(n):
		while len(s) and a[s[-1]] < a[i]:
			s.pop()
		lft.append(-1 if len(s) == 0 else s[-1])
		s.append(i)
	for i in reversed(range(n)):
		while len(s1) and a[s1[-1]] < a[i]:
			s1.pop()
		rig.append(n if len(s1) == 0 else s1[-1])
		s1.append(i)
	rig = rig[::-1]
	for i in range(n):
		l = lft[i] + 1
		r = rig[i] - 1
		if i - l < r - i:
			for j in range(l, i + 1):
				if a[i] % a[j] != 0:
					continue
				y = a[i] // a[j]
				if d.get(y) is None:
					continue
				z = d[y]
				if z < i or z > r:
					continue
				que.append([z + 1, -j - 1, -1])
		else:
			for j in range(i, r + 1):
				if a[i] % a[j] != 0:
					continue
				y = a[i] // a[j]
				if d.get(y) is None:
					continue
				z = d[y]
				if z > i or z < l:
					continue
				que.append([j + 1, -z - 1, -1])
	que.sort()
	ans = [0 for i in range(q)]
	bit = [0 for i in range(n + 2)]
	for i in range(len(que)):
		(l, r) = (-que[i][1], que[i][0])
		x = que[i][2]
		if x == -1:
			update(l, 1)
		else:
			ans[x] = get(r) - get(l - 1)
	for i in ans:
		print(i)


import sys
from bisect import bisect_right as lb
from collections import deque
from queue import PriorityQueue as pq
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()))
lii = lambda : list(map(int, list(ip())))
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()
inv = lambda x: pow(x, mod - 2, mod)
mod = 10 ** 9 + 7

def update(i, val):
	while i < len(bit):
		bit[i] += val
		i += i & -i

def get(i):
	ans = 0
	while i:
		ans += bit[i]
		i -= i & -i
	return ans
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	que = []
	for i in range(q):
		(l, r) = map(int, input().split())
		que.append([r, -l, i])
	d = {}
	for i in range(n):
		d[a[i]] = i
	(lft, rig, s, s1) = ([], [], [], [])
	for i in range(n):
		while len(s) > 0 and a[s[-1]] < a[i]:
			s.pop()
		if len(s) == 0:
			lft.append(-1)
		else:
			lft.append(s[-1])
		s.append(i)
	for i in range(n - 1, -1, -1):
		while len(s1) > 0 and a[s1[-1]] < a[i]:
			s1.pop()
		if len(s1) == 0:
			rig.append(n)
		else:
			rig.append(s1[-1])
		s1.append(i)
	rig = rig[::-1]
	for i in range(n):
		l = lft[i] + 1
		r = rig[i] - 1
		if i - l < r - i:
			for j in range(l, i + 1):
				if a[i] % a[j] != 0:
					continue
				y = a[i] // a[j]
				if d.get(y) is None:
					continue
				z = d[y]
				if z < i or z > r:
					continue
				que.append([z + 1, -j - 1, -1])
		else:
			for j in range(i, r + 1):
				if a[i] % a[j] != 0:
					continue
				y = a[i] // a[j]
				if d.get(y) is None:
					continue
				z = d[y]
				if z > i or z < l:
					continue
				que.append([j + 1, -z - 1, -1])
	que.sort()
	ans = [0 for i in range(q)]
	bit = [0 for i in range(n + 2)]
	for i in range(len(que)):
		(l, r) = (-que[i][1], que[i][0])
		x = que[i][2]
		if x == -1:
			update(l, 1)
		else:
			ans[x] = get(r) - get(l - 1)
	for i in ans:
		print(i)


import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs2(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
b = []
vis = []
tot = 0
time = []
time1 = []
adj = []
mx = -1
eps = 1e-07

def update_it(bit, i, val):
	n = len(bit)
	while i <= n:
		bit[i] += val
		i += i & -i

def get_ans(bit, i):
	n = len(bit)
	tot = 0
	while i > 0:
		tot += bit[i]
		i -= i & -i
	return tot

def hnbhai(tc):
	(n, q) = sd()
	a = sd()
	queries = []
	ans = [0] * q
	for i in range(q):
		(l, r) = sd()
		queries.append([r, -l, i])
	d = dict()
	for i in range(n):
		if d.get(a[i]) is None:
			d[a[i]] = []
		d[a[i]].append(i)
	left = []
	stck = []
	for i in range(n):
		while len(stck) > 0 and a[stck[-1]] < a[i]:
			stck.pop()
		if len(stck) == 0:
			left.append(-1)
		else:
			left.append(stck[-1])
		stck.append(i)
	right = []
	stck = []
	for i in range(n - 1, -1, -1):
		while len(stck) > 0 and a[stck[-1]] < a[i]:
			stck.pop()
		if len(stck) == 0:
			right.append(n)
		else:
			right.append(stck[-1])
		stck.append(i)
	right.reverse()
	for i in range(n):
		x = a[i]
		l = left[i] + 1
		r = right[i] - 1
		if abs(i - l) < abs(r - i):
			for j in range(l, i + 1):
				if x % a[j] != 0:
					continue
				y = x // a[j]
				if d.get(y) is None:
					continue
				idx = lb(d[y], i)
				if idx == len(d[y]):
					continue
				while idx < len(d[y]) and d[y][idx] <= r:
					queries.append([d[y][idx] + 1, -(j + 1), -1])
					idx += 1
		else:
			for j in range(i, r + 1):
				if x % a[j] != 0:
					continue
				y = x // a[j]
				if d.get(y) is None:
					continue
				idx = lb(d[y], l)
				if idx == len(d[y]):
					continue
				while idx < len(d[y]) and d[y][idx] <= i:
					queries.append([j + 1, -(d[y][idx] + 1), -1])
					idx += 1
	queries.sort()
	bit = [0] * (n + 2)
	for i in range(len(queries)):
		(l, r) = (-queries[i][1], queries[i][0])
		if queries[i][-1] == -1:
			update_it(bit, l, 1)
		else:
			ans[queries[i][-1]] = get_ans(bit, r) - get_ans(bit, l - 1)
	for i in ans:
		print(i)
for _ in range(sb()):
	hnbhai(_ + 1)