class SegmentTree:
def __init__(self, data, default=0, func=lambda x, y: x + y):
"""initialize the segment tree with 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):
"""func of data[start, stop)"""
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)
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
seg = SegmentTree([0] * 1000100)
l = list(map(int, input().split()))
for i in range(N - 1):
v1, v2 = l[i], l[i + 1]
v1, v2 = min(v1, v2), max(v1, v2)
seg[v1] += 1
seg[v2] -= 1
out = []
for _ in range(M):
t = tuple(map(int, input().split()))
if t[0] == 1:
p, v = t[1], t[2]
p -= 1
if p > 0:
v1, v2 = l[p], l[p - 1]
v1, v2 = min(v1, v2), max(v1, v2)
seg[v1] -= 1
seg[v2] += 1
if p < N - 1:
v1, v2 = l[p], l[p + 1]
v1, v2 = min(v1, v2), max(v1, v2)
seg[v1] -= 1
seg[v2] += 1
l[p] = v
if p > 0:
v1, v2 = l[p], l[p - 1]
v1, v2 = min(v1, v2), max(v1, v2)
seg[v1] += 1
seg[v2] -= 1
if p < N - 1:
v1, v2 = l[p], l[p + 1]
v1, v2 = min(v1, v2), max(v1, v2)
seg[v1] += 1
seg[v2] -= 1
else:
out.append(seg.query(0, t[1]))
print('\n'.join(map(str, out)))
