Firdavs is living on planet F. There are $N$ cities (numbered $1$ through $N$) on this planet; let's denote the value of city $i$ by $v_i$. Firdavs can travel directly from each city to any other city. When he travels directly from city $x$ to city $y$, he needs to pay $f(x, y) = |v_y-v_x|+y-x$ coins (this number can be negative, in which case he receives $-f(x, y)$ coins).
Let's define a simple path from city $x$ to city $y$ with length $k \ge 1$ as a sequence of cities $a_1, a_2, \ldots, a_k$ such that all cities in this sequence are different, $a_1 = x$ and $a_k = y$. The cost of such a path is $\sum_{i=1}^{k-1} f(a_i, a_{i+1})$.
You need to answer some queries for Firdavs. In each query, you are given two cities $x$ and $y$, and you need to find the minimum cost of a simple path from city $x$ to city $y$. Then, you need to find the length of the longest simple path from $x$ to $y$ with this cost.

-----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 $Q$.
- The second line contains $N$ space-separated integers $v_1, v_2, \ldots, v_N$.
- The following $Q$ lines describe queries. Each of these lines contains two space-separated integers $x$ and $y$.

-----Output-----
For each query, print a single line containing two space-separated integers ― the minimum cost and the maximum length.

-----Constraints-----
- $1 \le T \le 100$
- $1 \le N, Q \le 2 \cdot 10^5$
- $0 \le v_i \le 10^9$ for each valid $i$
- $1 \le x, y \le N$
- the sum of $N$ in all test cases does not exceed $5 \cdot 10^5$
- the sum of $Q$ in all test cases does not exceed $5 \cdot 10^5$

-----Subtasks-----
Subtask #1 (30 points):
- $1 \le N, Q \le 1,000$
- $v_1 < v_2 < \ldots < v_N$
- the sum of $N$ in all test cases does not exceed $5,000$
- the sum of $Q$ in all test cases does not exceed $5,000$
Subtask #2 (70 points): original constraints

-----Example Input-----
2
4 2
4 2 5 7
2 3
3 4
2 1
1 1
2 1

-----Example Output-----
4 3
3 2
-1 2

-----Explanation-----
Example case 1: For the first query, there are two paths with cost $4$ from city $2$ to city $3$:
- $2 \rightarrow 1 \rightarrow 3$: cost $(|4-2|+1-2)+(|5-4|+3-1) = 4$, length $3$
- $2 \rightarrow 3$: cost $|5-2|+3-2 = 4$, length $2$
All other paths have greater costs, so the minimum cost is $4$. Among these two paths, we want the one with greater length, which is $3$.

Difficulty: HARD
Tags: Sorting

Range queries

Complete search
Skill types: Sorting

Range queries

Complete search

Starter code:

Solutions:
from collections import Counter
from collections import defaultdict
for z in range(int(input())):
	(n, q) = map(int, input().split())
	v = list(map(int, input().split()))
	sv = sorted(v)
	d = defaultdict(int)
	c = Counter(v)
	for i in range(n):
		if i and sv[i] == sv[i - 1]:
			continue
		d[sv[i]] = i
	for i in range(q):
		(x, y) = map(int, input().split())
		x -= 1
		y -= 1
		m = y
		sm = x
		if v[x] > v[y]:
			m = x
			sm = y
		print(v[m] - v[sm] + y - x, end=' ')
		print(d[v[m]] - d[v[sm]] + c[v[m]])


import bisect
for _ in range(int(input())):
	(n, q) = list(map(int, input().split()))
	ar = list(map(int, input().split()))
	new = ar.copy()
	new.sort()
	for __ in range(q):
		(x, y) = list(map(int, input().split()))
		cost = abs(ar[y - 1] - ar[x - 1]) + y - x
		length = bisect.bisect_right(new, max(ar[y - 1], ar[x - 1]))
		length -= bisect.bisect_left(new, min(ar[x - 1], ar[y - 1]))
		print(cost, length)


t = int(input())
for i in range(t):
	(n, q) = input().split()
	cities = [int(x) for x in input().split()]
	cities_sort = cities.copy()
	cities_sort.sort()
	for j in range(int(q)):
		(q1, q2) = [int(x) for x in input().split()]
		a = cities[q1 - 1]
		b = cities[q2 - 1]
		if a > b:
			c = a
			a = b
			b = c
		pos_a = cities_sort[::1].index(a)
		pos_b = len(cities_sort) - 1 - cities_sort[::-1].index(b)
		print(q2 - q1 + b - a, pos_b - pos_a + 1)


import bisect as bs
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	v = [int(x) for x in input().split()]
	c = sorted(v)
	for i in range(q):
		(x, y) = map(int, input().split())
		print(abs(v[x - 1] - v[y - 1]) + y - x, bs.bisect_right(c, max(v[x - 1], v[y - 1]), 0, n) - bs.bisect_left(c, min(v[x - 1], v[y - 1]), 0, n))


import bisect
for _ in range(int(input())):
	(N, Q) = list(map(int, input().strip().split(' ')))
	V = list(map(int, input().strip().split(' ')))
	VV = sorted(V)
	for ___ in range(Q):
		(x, y) = list(map(int, input().strip().split(' ')))
		x -= 1
		y -= 1
		ans1 = abs(V[x] - V[y]) + (y - x)
		post1 = bisect.bisect_left(VV, min(V[x], V[y]))
		post2 = bisect.bisect_right(VV, max(V[x], V[y]))
		ans2 = post2 - post1
		print(ans1, ans2)


from collections import Counter
from itertools import accumulate
for _ in range(int(input())):
	(N, Q) = map(int, input().split())
	v = list(map(int, input().split()))
	cnts = Counter(v)
	w = sorted(cnts)
	cumulative = dict(zip(w, accumulate((cnts[i] for i in w))))
	for _ in range(Q):
		(x, y) = map(int, input().split())
		(a, b) = sorted([v[x - 1], v[y - 1]])
		print(str(b - a + y - x) + ' ' + str(cumulative[b] - cumulative[a] + cnts[a]))


t = int(input())
for _ in range(t):
	(n, q) = list(map(int, input().split()))
	v = list(map(int, input().split()))
	vv = v[:]
	vv = [[j, i] for (j, i) in enumerate(v)]
	vv.sort(key=lambda x: x[1])
	vvv = []
	for (jj, i) in enumerate(vv):
		v[i[0]] = [jj, i[1]]
	for i in range(q):
		(x, y) = list(map(int, input().split()))
		x -= 1
		y -= 1
		xx = v[x][0]
		yy = v[y][0]
		if xx < yy:
			le = yy - xx + 1
			cost = v[y][1] - v[x][1]
			cost += y - x
		elif xx == yy:
			le = 1
			cost = 0
		else:
			le = xx - yy + 1
			cost = v[x][1] - v[y][1]
			cost -= x - y
		print(cost, le)


for _ in range(int(input())):
	(n, q) = [int(a) for a in input().split()]
	v = list(map(int, input().split()))
	s = list(range(1, n + 1))
	index_s = [x for (_, x) in sorted(zip(v, s))]
	sorted_v = sorted(v)
	for i in range(q):
		(x, y) = [int(a) for a in input().split()]
		check1 = min(x, y)
		get_index1 = index_s.index(check1)
		vx = sorted_v[get_index1]
		check2 = max(x, y)
		get_index2 = index_s.index(max(x, y))
		vy = sorted_v[get_index2]
		length = get_index2 - get_index1 + 1
		ans = vy - vx + y - x
		print(ans, length)


T = int(input())
for i in range(0, T):
	(N, Q) = map(int, input().split())
	s = [int(x) for x in input().split()]
	L = sorted(s)
	G = L[::-1]
	for j in range(0, Q):
		(x, y) = map(int, input().split())
		ans1 = abs(s[y - 1] - s[x - 1]) + y - x
		print(ans1, end=' ')
		pos1 = 0
		pos2 = N
		for k in range(0, len(L)):
			if L[k] < min(s[x - 1], s[y - 1]):
				pos1 = k
			elif L[k] == min(s[x - 1], s[y - 1]):
				pos1 = k
				break
			else:
				break
		for k in range(0, len(L)):
			if G[k] > max(s[x - 1], s[y - 1]):
				pos2 = N - k - 1
			elif G[k] == max(s[x - 1], s[y - 1]):
				pos2 = N - k - 1
				break
			else:
				break
		print(pos2 - pos1 + 1)


t = int(input())
for i in range(t):
	(n, q) = list(map(int, input().split()))
	cities = list(map(int, input().split()))
	for j in range(int(q)):
		(q1, q2) = list(map(int, input().split()))
		a = cities[q1 - 1]
		b = cities[q2 - 1]
		if a > b:
			c = a
			a = b
			b = c
		size = 0
		for c in cities:
			if c >= a and c <= b:
				size += 1
		print(q2 - q1 + b - a, size)


import bisect as kk
T = int(input())
for i in range(0, T):
	(N, Q) = map(int, input().split())
	s = [int(x) for x in input().split()]
	L = sorted(s)
	for j in range(0, Q):
		(x, y) = map(int, input().split())
		ans1 = abs(s[y - 1] - s[x - 1]) + y - x
		print(ans1, end=' ')
		ans2 = kk.bisect_right(L, max(s[x - 1], s[y - 1])) - kk.bisect_left(L, min(s[x - 1], s[y - 1]))
		print(ans2)


def bs(arr, l, r, x, g):
	while l <= r:
		mid = l + (r - l) // 2
		if arr[mid] == x:
			if not g:
				mid -= 1
				while mid >= 0 and arr[mid] == x:
					mid -= 1
				return mid + 1
			else:
				mid += 1
				while mid <= r and arr[mid] == x:
					mid += 1
				return mid - 1
		elif arr[mid] < x:
			l = mid + 1
		else:
			r = mid - 1
	return -1
T = int(input())
for t in range(T):
	(N, Q) = map(int, input().split())
	V = list(map(int, input().split()))
	S = sorted(V)
	for q in range(Q):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		mini = min(V[b], V[a])
		maxi = max(V[b], V[a])
		C = b - a + (maxi - mini)
		f = bs(S, 0, N - 1, mini, False)
		L = 2 + bs(S, f, N - 1, maxi, True) - f - 1
		print(C, L)


import bisect
for _ in range(int(input())):
	(n, q) = [int(a) for a in input().split()]
	arr = list(map(int, input().split()))
	arr1 = sorted(arr)
	for i in range(q):
		(x, y) = [int(a) for a in input().split()]
		print(abs(arr[y - 1] - arr[x - 1]) + y - x, bisect.bisect_right(arr1, max(arr[y - 1], arr[x - 1])) - bisect.bisect_left(arr1, min(arr[x - 1], arr[y - 1])))


def query(x1, y1, d):
	(x, y) = (x1, y1)
	if d[y1][3] < d[x1][3]:
		(x, y) = (y1, x1)
	summ = y1 - x1 + abs(d[y][0] - d[x][0])
	mlen = d[y][2] - d[x][1] + 1
	return (summ, mlen)
INF = 10 ** 10
t = int(input())
for tt in range(t):
	(n, q) = [int(x) for x in input().split()]
	v = [int(x) for x in input().split()]
	v.append(INF)
	indexed = [(i, [x, 0, 0, 0]) for (x, i) in zip(v, range(1, n + 2))]
	indexed.sort(key=lambda x: x[1][0])
	scores = [x[1][0] for x in indexed]
	curr_left = 0
	curr_right = 0
	for i in range(1, n + 1):
		indexed[i][1][3] = i
		if scores[i] == scores[i - 1] and i != n:
			curr_right = i
			continue
		for j in range(curr_left, curr_right + 1):
			indexed[j][1][1] = curr_left
			indexed[j][1][2] = curr_right
		curr_left = i
		curr_right = i
	d = dict(indexed)
	for qq in range(q):
		(x, y) = [int(x) for x in input().split()]
		ans = query(x, y, d)
		print(ans[0], end=' ')
		print(ans[1])