You have an array A of length N. In one operation, you can do the following: 
Select any subarray A_{L \ldots R} (1 ≤ L ≤ R ≤ N) and then add i to the i-th element of this subarray. Formally, we set A_{j} := A_{j} + (j - L + 1) for all L ≤ j ≤ R.

For example: if A = [2, 1, 5, 2] and we apply operation on A_{2 \ldots 4} then A becomes [2, 1 + 1, 5 + 2, 2 + 3] = [2, 2, 7, 5].

The minimum number of such operations required to sort A in non-decreasing order is termed as the goodness of A.

We want to process Q updates on A of the following form:
\texttt{i x} : Set A_{i} := x where (1 ≤ i ≤ N).

Determine the goodness of A after each update.

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains two integers N and Q — the size of the array A and the number of updates.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A.
- The next Q lines each contain two integers i and x denoting the parameters of the update.

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

For each test case, output Q integers, the goodness of the array after each update.

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

$1 ≤ T ≤ 10^{4}$
$2 ≤ N ≤ 10^{5}$
$1 ≤Q ≤N$
$1 ≤A_{i} ≤10^{9}$
$1 ≤x ≤10^{9}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

------ subtasks ------ 

Subtask 1 (50 points): $1 ≤Q ≤\min(5, N)$
Subtask 2 (50 points): Original constraints.

----- Sample Input 1 ------ 
2
3 2
3 2 1
3 10
2 1
4 2
2 2 2 2
4 2
4 1

----- Sample Output 1 ------ 
1
2
0
1

----- explanation 1 ------ 
Test Case 1: Initially $A = [3, 2, 1]$.
- After first update: $A = [3, 2, 10]$. 
- Now we can apply the operation on $A_{1 \ldots 2}$. Then $A$ becomes $[4, 4, 10]$. Therefore the goodness of $A$ is $1$.
- After second update: $A = [3, 1, 10]$. 
-  Now we can apply the operation on $A_{2 \ldots 2}$. $A$ becomes $[3, 2, 10]$. Now again we can apply the operation $A_{2 \ldots 2}$. $A$ becomes $[3, 3, 10]$. Therefore the goodness of $A$ is $2$.

Test Case 2: Initially $A = [2, 2, 2, 2]$.
- After first update: $A = [2, 2, 2, 2]$. 
- $A$ is already in sorted order. Therefore the goodness of $A$ is $0$.
- After second update: $A = [2, 2, 2, 1]$. 
-  Now we can apply the operation on $A_{3 \ldots 4}$. $A$ becomes $[2, 2, 3, 3]$. Therefore the goodness of $A$ is $1$.

Difficulty: HARD
Tags: Constructive algorithms

Data structures

Mathematics

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
from bisect import *
from heapq import *
from math import *
from collections import defaultdict as ddc
from collections import Counter
from functools import reduce

def intin():
	return int(input())

def mapin():
	return map(int, input().split())

def strin():
	return input().split()
INF = 10 ** 20
mod = 1000000007

def hashit(arr, size, mod=10 ** 9 + 7):
	if not size:
		return
	(mul, hashh, div) = (256, 0, (1 << 8 * size - 8) % mod)
	C = defaultdict(list)
	for i in range(size):
		hashh = (mul * hashh + arr[i]) % mod
	C[hashh].append(0)
	for i in range(len(arr) - size):
		hashh = (mul * (hashh - arr[i] * div) + arr[i + size]) % mod
		C[hashh].append(i + 1)
	return C

def LIS(arr, n):
	dp = [10 ** 9] * (n + 1)
	for ele in arr:
		dp[bisect_left(dp, ele)] = ele
	return bisect_left(dp, 10 ** 9)

def exponentiation(bas, exp, mod=10 ** 9 + 7):
	t = 1
	while exp > 0:
		if exp % 2 != 0:
			t = t * bas % mod
		bas = bas * bas % mod
		exp //= 2
	return t % mod

def MOD(p, q=1, mod=1000000007):
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p
yes = 'YES'
no = 'NO'
even = 'EVEN'
odd = 'ODD'

def graphin(n):
	zz = defaultdict(set)
	for i in range(n - 1):
		(a, b) = mapin()
		zz[a].add(b)
		zz[b].add(a)
	return zz

def process(arr, n, Q):
	h = []
	heappush(h, [0, 0])
	for i in range(1, n):
		temp = arr[i - 1] - arr[i]
		heappush(h, [-temp, i])
	for (i, x) in Q:
		arr[i - 1] = x
		if i > 1:
			temp = arr[i - 2] - arr[i - 1]
			heappush(h, [-temp, i - 1])
		if i < n:
			temp = arr[i - 1] - arr[i]
			heappush(h, [-temp, i])
		while h:
			(val, i) = heappop(h)
			if arr[i] - arr[i - 1] == val or i == 0:
				if val > 0:
					print(0)
				else:
					print(-val)
				heappush(h, [val, i])
				break

def main():
	for _ in range(int(input())):
		(n, q) = mapin()
		arr = list(mapin())
		Q = []
		for i in range(q):
			(i, x) = mapin()
			Q.append([i, x])
		process(arr, n, Q)
main()


T = int(input())
for t in range(T):
	(N, Q) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	maximo = max([0] + [a - b for (a, b) in zip(A, A[1:])])
	for q in range(Q):
		recalculate = False
		(i, x) = list(map(int, input().split()))
		i -= 1
		if i > 0 and maximo == A[i - 1] - A[i]:
			recalculate = True
		if i < N - 1 and maximo == A[i] - A[i + 1]:
			recalculate = True
		A[i] = x
		if recalculate:
			maximo = max([0] + [a - b for (a, b) in zip(A, A[1:])])
		else:
			if i > 0:
				maximo = max(maximo, A[i - 1] - A[i])
			if i < N - 1:
				maximo = max(maximo, A[i] - A[i + 1])
		print(maximo)


for i in range(int(input())):
	(n, q) = map(int, input().split())
	ar = list(map(int, input().split()))
	maxi = max([0] + [ar[i] - ar[i + 1] for i in range(n - 1)])
	for i in range(q):
		(i, val) = map(int, input().split())
		i -= 1
		if i > 0 and ar[i - 1] - ar[i] == maxi or (i + 1 < n and ar[i] - ar[i + 1] == maxi):
			ar[i] = val
			maxi = max([0] + [ar[i] - ar[i + 1] for i in range(n - 1)])
		else:
			ar[i] = val
			if i > 0:
				maxi = max(maxi, ar[i - 1] - ar[i])
			if i + 1 < n:
				maxi = max(maxi, ar[i] - ar[i + 1])
		print(maxi)


for i in range(int(input())):
	(n, q) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	maximo = max([0] + [a - b for (a, b) in zip(a, a[1:])])
	for j in range(q):
		recalculate = False
		(i, x) = list(map(int, input().split()))
		i -= 1
		if i > 0 and maximo == a[i - 1] - a[i]:
			recalculate = True
		if i < n - 1 and maximo == a[i] - a[i + 1]:
			recalculate = True
		a[i] = x
		if recalculate:
			maximo = max([0] + [a - b for (a, b) in zip(a, a[1:])])
		else:
			if i > 0:
				maximo = max(maximo, a[i - 1] - a[i])
			if i < n - 1:
				maximo = max(maximo, a[i] - a[i + 1])
		print(maximo)


for _ in range(int(input())):
	(N, Q) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	maxi = max([0] + [a - b for (a, b) in zip(A, A[1:])])
	for q in range(Q):
		recalculate = False
		(i, x) = list(map(int, input().split()))
		i -= 1
		if i > 0 and maxi == A[i - 1] - A[i]:
			recalculate = True
		if i < N - 1 and maxi == A[i] - A[i + 1]:
			recalculate = True
		A[i] = x
		if recalculate:
			maxi = max([0] + [a - b for (a, b) in zip(A, A[1:])])
		else:
			if i > 0:
				maxi = max(maxi, A[i - 1] - A[i])
			if i < N - 1:
				maxi = max(maxi, A[i] - A[i + 1])
		print(maxi)


from collections import *
from itertools import *
from functools import *
from heapq import *
import sys, math
input = sys.stdin.readline

def segfunc(x, y):
	return max(x, y)
ide_ele = -(1 << 30)

class SegTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res

def answer():
	(N, Q) = map(int, input().split())
	A = list(map(int, input().split()))
	B = [A[i] - A[i + 1] for i in range(N - 1)]
	T = SegTree(B, segfunc, ide_ele)
	for _ in range(Q):
		(i, x) = map(int, input().split())
		i -= 1
		A[i] = x
		if i == 0:
			T.update(0, A[i] - A[i + 1])
		elif i == N - 1:
			T.update(N - 2, A[N - 2] - A[N - 1])
		else:
			T.update(i - 1, A[i - 1] - A[i])
			T.update(i, A[i] - A[i + 1])
		print(max(T.query(0, N - 1), 0))
for _ in range(int(input())):
	answer()


T = int(input())
for _ in range(T):
	(N, Q) = map(int, input().split())
	A = list(map(int, input().split()))
	goodness = 0
	for j in range(N - 1):
		goodness = max(goodness, A[j] - A[j + 1])
	for q in range(Q):
		(i, x) = map(int, input().split())
		change = False
		if i > 1 and goodness == A[i - 2] - A[i - 1]:
			change = True
		if i < N and goodness == A[i - 1] - A[i]:
			change = True
		A[i - 1] = x
		if change:
			goodness = 0
			for j in range(N - 1):
				goodness = max(goodness, A[j] - A[j + 1])
		else:
			if i > 1:
				goodness = max(goodness, A[i - 2] - A[i - 1])
			if i < N:
				goodness = max(goodness, A[i - 1] - A[i])
		print(goodness)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	l1 = list(map(int, input().split()))
	maximo = max([0] + [a - b for (a, b) in zip(l1, l1[1:])])
	for blah in range(q):
		(i, xy) = list(map(int, input().split()))
		i -= 1
		rc = False
		if i > 0 and maximo == l1[i - 1] - l1[i]:
			rc = True
		if i < n - 1 and maximo == l1[i] - l1[i + 1]:
			rc = True
		l1[i] = xy
		if rc:
			maximo = max([0] + [a - b for (a, b) in zip(l1, l1[1:])])
		else:
			if i > 0:
				maximo = max(maximo, l1[i - 1] - l1[i])
			if i < n - 1:
				maximo = max(maximo, l1[i] - l1[i + 1])
		print(maximo)


from heapq import heapify, heappop, heappush
t = int(input())
for _ in range(t):
	(N, Q) = map(int, input().split())
	A = list(map(int, input().split()))
	h = {}
	mh = []
	for i in range(N - 1):
		if A[i] > A[i + 1]:
			mh.append(-(A[i] - A[i + 1]))
		h[A[i] - A[i + 1]] = 1 + h.get(A[i] - A[i + 1], 0)
	heapify(mh)
	for q in range(Q):
		(i, x) = map(int, input().split())
		i -= 1
		if i < N - 1:
			h[A[i] - A[i + 1]] -= 1
			h[x - A[i + 1]] = 1 + h.get(x - A[i + 1], 0)
			heappush(mh, -(x - A[i + 1]))
		if i > 0:
			h[A[i - 1] - A[i]] -= 1
			h[A[i - 1] - x] = 1 + h.get(A[i - 1] - x, 0)
			heappush(mh, -(A[i - 1] - x))
		A[i] = x
		while h[-mh[0]] == 0:
			heappop(mh)
		print(-mh[0] if mh[0] < 0 else 0)


from sys import maxsize
INT_MIN = -maxsize

def construct_segment_tree(a: list, n: int, segtree):
	for i in range(n):
		segtree[n + i] = a[i]
	for i in range(n - 1, 0, -1):
		segtree[i] = max(segtree[2 * i], segtree[2 * i + 1])

def update(pos: int, value: int, n: int, segtree):
	pos += n
	segtree[pos] = value
	while pos > 1:
		pos //= 2
		segtree[pos] = max(segtree[2 * pos], segtree[2 * pos + 1])

def range_query(left: int, right: int, n: int, segtree) -> int:
	left += n
	right += n
	ma = INT_MIN
	while left < right:
		if left & 1:
			ma = max(ma, segtree[left])
			left += 1
		if right & 1:
			right -= 1
			ma = max(ma, segtree[right])
		left //= 2
		right //= 2
	return ma
t = int(input())
for _ in range(t):
	(N, Q) = map(int, input().split())
	A = list(map(int, input().split()))
	res = []
	for i in range(N - 1):
		res.append(A[i] - A[i + 1])
	tree = [0] * (2 * len(res))
	construct_segment_tree(res, len(res), tree)
	for q in range(Q):
		(i, x) = map(int, input().split())
		i -= 1
		if i == 0:
			update(i, x - A[i + 1], N - 1, tree)
		elif i == N - 1:
			update(i - 1, A[i - 1] - x, N - 1, tree)
		else:
			update(i - 1, A[i - 1] - x, N - 1, tree)
			update(i, x - A[i + 1], N - 1, tree)
		A[i] = x
		res = max(0, range_query(0, N - 1, N - 1, tree))
		print(res)


from heapq import heappop, heappush
t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	heap = []
	d = {}
	for i in range(1, n):
		if arr[i - 1] > arr[i]:
			diff = arr[i - 1] - arr[i]
			heappush(heap, -diff)
			if diff not in d:
				d[diff] = 0
			d[diff] += 1
	for j in range(q):
		(index, ele) = map(int, input().split())
		index -= 1
		if index != 0 and arr[index] < arr[index - 1]:
			diff = arr[index - 1] - arr[index]
			if d[diff] != 0:
				d[diff] -= 1
		if index != n - 1 and arr[index] > arr[index + 1]:
			diff = arr[index] - arr[index + 1]
			if d[diff] != 0:
				d[diff] -= 1
		arr[index] = ele
		if index != 0 and arr[index] < arr[index - 1]:
			diff = arr[index - 1] - arr[index]
			if diff not in d or d[diff] == 0:
				heappush(heap, -diff)
				d[diff] = 0
			d[diff] += 1
		if index != n - 1 and arr[index] > arr[index + 1]:
			diff = arr[index] - arr[index + 1]
			if diff not in d or d[diff] == 0:
				heappush(heap, -diff)
				d[diff] = 0
			d[diff] += 1
		while heap:
			diff = -1 * heappop(heap)
			if d[diff] != 0:
				heappush(heap, -1 * diff)
				break
		if heap:
			print(-1 * heap[0])
		else:
			print(0)


t = int(input())
for _ in range(t):
	(N, Q) = map(int, input().split())
	arrA = list(map(int, input().split()))
	ops_count = 0
	index = -1
	compute = False
	for inp in range(Q):
		(i, x) = map(int, input().split())
		arrA[i - 1] = x
		if i == index + 1 or i == index + 2:
			compute = True
		init_total_ops = 0
		if inp == 0 or compute:
			compute = False
			incre = 0
			max_diff = 0
			for it in range(N - 1):
				ele1 = arrA[it]
				ele2 = arrA[it + 1]
				temp_diff = ele1 - ele2
				if max_diff < temp_diff:
					max_diff = temp_diff
					index = it
			ops_count = max_diff
		elif i == 1:
			if arrA[0] > arrA[1]:
				diff = arrA[0] - arrA[1]
				if diff > ops_count:
					ops_count = diff
					index = 0
		elif i == N:
			if arrA[N - 2] > arrA[N - 1]:
				diff = arrA[N - 2] - arrA[N - 1]
				if diff > ops_count:
					ops_count = diff
					index = N - 2
		elif arrA[i - 2] > arrA[i - 1] or arrA[i - 1] > arrA[i]:
			if arrA[i - 2] - arrA[i - 1] > arrA[i - 1] - arrA[i]:
				diff = arrA[i - 2] - arrA[i - 1]
				if diff > ops_count:
					ops_count = diff
					index = i - 2
			else:
				diff = arrA[i - 1] - arrA[i]
				if diff > ops_count:
					ops_count = diff
					index = i - 1
		print(ops_count)


from collections import defaultdict

def goodness(A, idx, ans, mp, mpp):
	nxt = ans
	if idx > 0:
		mpp[mp[idx]] = max(mpp[mp[idx]] - 1, 0)
		sol = max(0, A[idx - 1] - A[idx])
		mp[idx] = sol
		mpp[sol] += 1
		nxt = max(nxt, sol)
	if idx < len(A) - 1:
		mpp[mp[idx + 1]] = max(mpp[mp[idx + 1]] - 1, 0)
		sol = max(0, A[idx] - A[idx + 1])
		mp[idx + 1] = sol
		mpp[sol] += 1
		nxt = max(nxt, sol)
	if nxt > ans:
		return (nxt, mp, mpp)
	elif mpp[ans] > 0:
		return (ans, mp, mpp)
	maxx = 0
	for (x, y) in mpp.items():
		if y > 0:
			maxx = max(maxx, x)
	return (maxx, mp, mpp)

def solve():
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	mp = defaultdict(int)
	mpp = defaultdict(int)
	ans = 0
	for i in range(1, len(A)):
		sol = max(0, A[i - 1] - A[i])
		mp[i] = sol
		mpp[sol] += 1
		ans = max(ans, sol)
	for _ in range(m):
		(a, b) = map(int, input().split())
		A[a - 1] = b
		(ans, mp, mpp) = goodness(A, a - 1, ans, mp, mpp)
		print(ans)
for _ in range(int(input())):
	solve()


import sys
import heapq as hp

class Obj(object):

	def __init__(self, diff, indx):
		self.val = (diff, indx)

	def __lt__(self, other):
		return self.val[0] > other.val[0]

def print(a):
	sys.stdout.write(str(a) + '\n')

def input():
	return sys.stdin.readline()
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	d = {}
	h = []
	for i in range(1, n):
		diff = l[i - 1] - l[i]
		hp.heappush(h, Obj(diff, i))
	for w in range(k):
		(x, y) = map(int, input().split())
		x -= 1
		l[x] = y
		if x > 0:
			nd1 = l[x - 1] - l[x]
			hp.heappush(h, Obj(nd1, x))
		if x < n - 1:
			nd2 = l[x] - l[x + 1]
			hp.heappush(h, Obj(nd2, x + 1))
		while True:
			(dif, ind) = h[0].val
			if l[ind - 1] - l[ind] == dif:
				print(max(0, dif))
				break
			hp.heappop(h)


import numpy as np
from heapq import heapify, heappush, heappop

def ggt(A):
	goodness_tata = list(np.diff(A))
	heapify(goodness_tata)
	return goodness_tata

def ugt(A, goodness_tata, cheap, i, x):
	if i - 1:
		heappush(goodness_tata, x - A[i - 2])
		heappush(cheap, A[i - 1] - A[i - 2])
	if i < len(A):
		heappush(goodness_tata, A[i] - x)
		heappush(cheap, A[i] - A[i - 1])
	A[i - 1] = x

def sgt(goodness_tata, cheap):
	s = goodness_tata[0]
	while cheap and s == cheap[0]:
		heappop(goodness_tata)
		heappop(cheap)
		s = goodness_tata[0]
	return s * -int(s < 0)
T = int(input())
for i in range(T):
	(N, Q) = map(int, input().split())
	A = np.array(input().split(), dtype=int)
	goodness_tata = ggt(A)
	cheap = []
	for j in range(Q):
		(i, x) = map(int, input().split())
		ugt(A, goodness_tata, cheap, i, x)
		print(sgt(goodness_tata, cheap))


T = int(input())

def findMax(p):
	(ans1, ans2) = (set(), 0)
	for i in range(len(p)):
		if p[i] > ans2:
			ans1 = {i}
			ans2 = p[i]
		elif p[i] == ans2:
			ans1.add(i)
		else:
			pass
	return (ans1, ans2)

def updateMax(maxSet, maxValue, index, value):
	if value < maxValue:
		if index in maxSet:
			maxSet.remove(index)
		else:
			pass
	elif value == maxValue:
		maxSet.add(index)
	else:
		maxSet = {index}
		maxValue = value
	return (maxSet, maxValue)
for _ in range(T):
	(n, q) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	arr = [0] * n
	for i in range(1, n):
		arr[i] = max(a[i - 1] - a[i], 0)
	(maxSet, maxVal) = findMax(arr)
	for __ in range(q):
		(i, x) = [int(x) for x in input().split()]
		a[i - 1] = x
		if i != 1:
			arr[i - 1] = max(a[i - 2] - x, 0)
			(maxSet, maxVal) = updateMax(maxSet, maxVal, i - 1, arr[i - 1])
			if len(maxSet) == 0:
				(maxSet, maxVal) = findMax(arr)
		if i != n:
			arr[i] = max(x - a[i], 0)
			(maxSet, maxVal) = updateMax(maxSet, maxVal, i, arr[i])
			if len(maxSet) == 0:
				(maxSet, maxVal) = findMax(arr)
		print(maxVal)