MoEngage has given you an array A consisting of N positive integers.

You should perform Q queries of the following two types:

1 i X : Set A_{i} to X.
2 L R : Find the minimum non-negative integer K such that the sequence [|A_{L} - K|, |A_{L+1} - K|, \ldots, |A_{R-1} - K|, |A_{R} - K|] is sorted in non-decreasing order. Print -1 if no such K exists.

For each query of type 2, output the minimum non-negative integer K satisfying the constraint, or -1 if there isn't any.

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

- The first line contains two integers N, Q.
- The second line contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N}.
- Then, the i^{th} of the next Q lines contains three integers describing the queries 1 i X or 2 L R.

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

For each query of type 2, output the minimum integer K satisfying the constraint, or -1 if there isn't any in a new line.

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

$1 ≤ N, Q ≤ 2\cdot 10^{5}$
$0 ≤ A_{i}, X ≤ 10^{9}$
$1 ≤ L ≤ R ≤ N$

----- Sample Input 1 ------ 
5 7
5 3 2 6 0
2 1 5
1 2 7
2 1 5
1 4 2
2 1 5
1 2 5
2 1 2
----- Sample Output 1 ------ 
4
-1
5
0

----- explanation 1 ------ 
- In the first query, selecting $K=4$ makes the sequence $[|A_{1} - K|, |A_{2} - K|, |A_{3} - K|, |A_{4} - K|, |A_{5} - K|] = [1, 1, 2, 2, 4]$. This sequence is sorted in non-decreasing order. Also, there exists no value of $K$ less than $4$ satisfying this.

- In the second query, change $A_{2} = 7$. After the second query, the array $A$ becomes $[5, 7, 2, 6, 0]$.

- In the third query, there exists no value of $K$ satisfying the constraints.

Source: codechef | Difficulty: VERY_HARD
Tags: Data structures

Range queries

Segment trees revisited


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

def merge(p1, p2):
	if p1[-1] == -1:
		return p2
	if p2[2] == -1:
		return p1
	if p1[-1] == p2[2]:
		interval = (0, float('inf'))
	elif p1[-1] < p2[2]:
		interval = (0, (p1[-1] + p2[2]) // 2)
	else:
		interval = ((p1[-1] + p2[2]) // 2 + (p1[-1] + p2[2]) % 2, float('inf'))
	return (max(p1[0], p2[0], interval[0]), min(p1[1], p2[1], interval[1]), p1[2], p2[-1])

class SegmentTree:

	def __init__(self, data, default=(0, float('inf'), -1, -1), func=merge):
		data = [default] + data
		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):
		stop += 1
		start += self._size
		stop += self._size
		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 = 1
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	ST = SegmentTree([(0, float('inf'), arr[l], arr[l]) for l in range(n)])
	for M in range(m):
		(a, b, c) = map(int, input().split())
		if a == 1:
			ST.__setitem__(b, (0, float('inf'), c, c))
		else:
			(l, r, x, y) = ST.query(b, c)
			if l > r:
				l = -1
			print(l)


from sys import stdin, stdout
input = stdin.readline

def merge(p1, p2):
	if p1[-1] == -1:
		return p2
	if p2[2] == -1:
		return p1
	if p1[-1] == p2[2]:
		interval = (0, float('inf'))
	elif p1[-1] < p2[2]:
		interval = (0, (p1[-1] + p2[2]) // 2)
	else:
		interval = ((p1[-1] + p2[2]) // 2 + (p1[-1] + p2[2]) % 2, float('inf'))
	return (max(p1[0], p2[0], interval[0]), min(p1[1], p2[1], interval[1]), p1[2], p2[-1])

def build(ST, pos, l, r):
	if l == r:
		ST[pos] = (0, float('inf'), arr[l], arr[l])
		return ST[pos]
	mid = (l + r) // 2
	ST[pos] = merge(build(ST, 2 * pos + 1, l, mid), build(ST, 2 * pos + 2, mid + 1, r))
	return ST[pos]

def update(ST, pos, l, r, ind, val):
	if l == r:
		assert l == ind
		arr[l] = val
		ST[pos] = (0, float('inf'), arr[l], arr[l])
		return
	mid = (l + r) // 2
	if ind <= mid:
		update(ST, 2 * pos + 1, l, mid, ind, val)
	else:
		update(ST, 2 * pos + 2, mid + 1, r, ind, val)
	ST[pos] = merge(ST[2 * pos + 1], ST[2 * pos + 2])

def query(ST, pos, l, r, ql, qr):
	if ql <= l and r <= qr:
		return ST[pos]
	if r < ql or qr < l:
		return (0, float('inf'), -1, -1)
	mid = (l + r) // 2
	return merge(query(ST, 2 * pos + 1, l, mid, ql, qr), query(ST, 2 * pos + 2, mid + 1, r, ql, qr))
t = 1
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	ST = [(float('inf'), 0) for i in range(4 * n)]
	build(ST, 0, 0, n - 1)
	for M in range(m):
		(a, b, c) = map(int, input().split())
		if a == 1:
			b -= 1
			update(ST, 0, 0, n - 1, b, c)
		else:
			b -= 1
			c -= 1
			(l, r, x, y) = query(ST, 0, 0, n - 1, b, c)
			if l > r:
				l = -1
			print(l)