#include<bits/stdc++.h>
using namespace std;
const int MN = 200010;
int N, M;
int A[MN];
struct Query {
int t, x, y;
};
Query query[MN];
int Xn;
vector<int> X;
map<int, int> dx;
vector<int> V[MN << 1];
int chk[MN << 1], ans[MN << 1];
struct BIT {
vector<int> tree;
void init() {
tree = vector<int>(4 * Xn, 0);
}
void upd(int a, int b, int d, int l, int r, int n) {
if(b < l || r < a) return;
if(a <= l && r <= b) {
tree[n] += d;
return;
}
int m = (l + r)>>1;
upd(a, b, d, l, m, 2*n);
upd(a, b, d, m + 1, r, 2*n + 1);
}
int quer(int idx, int l, int r, int n) {
if(idx < l || r < idx) return 0;
int ret = tree[n];
if(l == r) return ret;
int m = (l + r)>>1;
int L = quer(idx, l, m, 2*n);
int R = quer(idx, m + 1, r, 2*n + 1);
return ret + L + R;
}
} bit;
void rem(int idx, int val) {
int cnt = 1;
if(idx && A[idx - 1] >= val) cnt--;
if(idx < N - 1 && A[idx + 1] >= val) cnt--;
bit.upd(0, val, -cnt, 0, Xn - 1, 1);
if(idx && A[idx - 1] < val) {
bit.upd(0, A[idx - 1], 1, 0, Xn - 1, 1);
}
if(idx < N - 1 && A[idx + 1] < val) {
bit.upd(0, A[idx + 1], 1, 0, Xn - 1, 1);
}
}
void add(int idx, int val) {
int cnt = 1;
if(idx && A[idx - 1] >= val) cnt--;
if(idx < N - 1 && A[idx + 1] >= val) cnt--;
bit.upd(0, val, cnt, 0, Xn - 1, 1);
if(idx && A[idx - 1] < val) {
bit.upd(0, A[idx - 1], -1, 0, Xn - 1, 1);
}
if(idx < N - 1 && A[idx + 1] < val) {
bit.upd(0, A[idx + 1], -1, 0, Xn - 1, 1);
}
}
int main() {
scanf("%d %d", &N, &M);
for(int i = 0; i < N; i++) {
scanf("%d", &A[i]);
X.push_back(A[i]);
}
for(int i = 0; i < M; i++) {
int t; scanf("%d", &t);
if(t == 1) {
int x; scanf("%d", &x);
query[i] = {t, x, -1};
X.push_back(x);
}
if(t == 2) {
int c, d; scanf("%d %d", &c, &d);
c--;
query[i] = {t, c, d};
X.push_back(d);
}
}
sort(X.begin(), X.end());
X.resize(unique(X.begin(), X.end()) - X.begin());
Xn = X.size();
for(int i = 0; i < Xn; i++) dx[X[i]] = i;
for(int i = 0; i < N; i++) {
A[i] = dx[A[i]];
}
for(int i = 0; i < M; i++) {
if(query[i].t == 1) {
query[i].x = dx[ query[i].x ];
}
if(query[i].t == 2) {
query[i].y = dx[ query[i].y ];
}
}
for(int i = 0; i < N; i++) {
V[ A[i] ].push_back(i);
}
int cnt = 0;
for(int i = Xn - 1; i >= 0; i--) {
for(int j = 0; j < V[i].size(); j++) {
cnt++;
if(V[i][j] > 0 && chk[ V[i][j] - 1 ]) cnt--;
if(chk[ V[i][j] + 1 ]) cnt--;
chk[ V[i][j] ] = 1;
}
ans[i] = cnt;
}
bit.init();
for(int i = 0; i < M; i++) {
int t = query[i].t;
int x = query[i].x;
int y = query[i].y;
if(t == 1) {
printf("%d\n", ans[x] + bit.quer(x, 0, Xn - 1, 1));
}
if(t == 2) {
int z = A[x];
rem(x, z);
add(x, y);
A[x] = y;
}
}
}
