#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
int N, Q;
int qu[202020], X[202020], Y[202020];
int A[202020];
int T[1505050];
vector<int> comp;
int com(int x){return lower_bound(comp.begin(), comp.end(), x)-comp.begin()+1;}
void update(int id, int s, int e, int ts, int te, int v){
if (e < ts || te < s) return;
if (ts <= s && e <= te){
T[id] += v;
return;
}
int mid = (s+e)/2;
update(id*2, s, mid, ts, te, v);
update(id*2+1, mid+1, e, ts, te, v);
}
int query(int id, int s, int e, int t){
if (e < t || t < s) return 0;
if (s == e) return T[id];
int mid = (s+e)/2;
return query(id*2, s, mid, t) + query(id*2+1, mid+1, e, t) + T[id];
}
int main(){
scanf("%d %d", &N, &Q);
for (int i=1; i<=N; i++){
scanf("%d", &A[i]);
comp.push_back(A[i]);
}
for (int i=1; i<=Q; i++){
scanf("%d", &qu[i]);
scanf("%d", &X[i]);
comp.push_back(X[i]);
if (qu[i] == 2){
scanf("%d", &Y[i]);
comp.push_back(Y[i]);
}
}
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
for (int i=1; i<=N; i++) {
A[i] = com(A[i]);
update(1, 1, comp.size(), min(A[i], A[i-1])+1, max(A[i], A[i-1]), 1);
}
update(1, 1, comp.size(), 1, A[N], 1);
for (int i=1; i<=Q; i++){
if (qu[i] == 1) printf("%d\n", query(1, 1, comp.size(), com(X[i])) / 2);
else {
update(1, 1, comp.size(), min(A[X[i]], A[X[i]-1])+1, max(A[X[i]], A[X[i]-1]), -1);
update(1, 1, comp.size(), min(A[X[i]], A[X[i]+1])+1, max(A[X[i]], A[X[i]+1]), -1);
A[X[i]] = com(Y[i]);
update(1, 1, comp.size(), min(A[X[i]], A[X[i]-1])+1, max(A[X[i]], A[X[i]-1]), 1);
update(1, 1, comp.size(), min(A[X[i]], A[X[i]+1])+1, max(A[X[i]], A[X[i]+1]), 1);
}
}
return 0;
}
