#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m, a[200200], t[1001001], N;
vector<int> X;
vector<array<int, 2>> query;
void update(int b, int x) {
while(b <= N) t[b] += x, b += b & -b;
}
int find(int b) {
int re = 0;
while(b) re += t[b], b -= b & -b;
return re;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=1;i<=n;i++) X.push_back(a[i]), X.push_back(a[i]+1);
for(int i=1;i<=m;i++) {
int q; cin >> q;
if(q == 1) {
int x; cin >> x;
X.push_back(x);
query.push_back({0, x});
} else {
int x, y; cin >> x >> y;
X.push_back(y), X.push_back(y);
query.push_back({x, y});
}
}
sort(X.begin(), X.end()), X.erase(unique(X.begin(), X.end()), X.end());
N = X.size();
for(int i=1;i<=n;i++) a[i] = lower_bound(X.begin(), X.end(), a[i]) - X.begin() + 1;
for(int i=1;i<n;i++) if(a[i] != a[i+1]) update(min(a[i], a[i+1])+1, 1), update(max(a[i], a[i+1])+1, -1);
for(auto [x, y] : query) {
y = lower_bound(X.begin(), X.end(), y) - X.begin() + 1;
if(x) {
for(int i=max(1,x-1);i<=min(n-1,x);i++) if(a[i] != a[i+1]) {
update(min(a[i], a[i+1])+1, -1), update(max(a[i], a[i+1])+1, 1);
}
a[x] = y;
for(int i=max(1,x-1);i<=min(n-1,x);i++) if(a[i] != a[i+1]) {
update(min(a[i], a[i+1])+1, 1), update(max(a[i], a[i+1])+1, -1);
}
} else {
int k = find(y);
if(a[1] >= y) cout << (k+2)/2 << "\n";
else cout << (k+1)/2 << "\n";
}
}
}
