#include <bits/stdc++.h>
#define task "BriantheCrab"
#define int long long
#define pii pair <int, int>
#define fi first
#define se second
#define szf sizeof
#define sz(s) (int)((s).size())
#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
template <class T> void minimize (T &t, T f) {if (t > f) t = f;}
template <class T> void maximize (T &t, T f) {if (t < f) t = f;}
const int maxN = 2e5 + 5;
const int inf = 1e18 + 7;
const int mod = 1e9 + 7;
// khong tu code thi khong kha len duoc dau
// biet sol roi thi tu lam not di
struct ST {
vector <int> st, lazy;
void init (int _n) {
st.resize (_n * 4, 0);
lazy.resize (_n * 4, 0);
}
void push (int id, int l, int r) {
int &t = lazy[id];
int mid = (l + r) >> 1;
if (t != 0) {
st[id * 2] += t * (l - mid + 1);
lazy[id * 2] += t;
st[id * 2 + 1] += t * (r - mid);
lazy[id * 2 + 1] += t;
}
t = 0;
}
void upd (int id, int l, int r, int u, int v, int val) {
if (v < l || u > r) {
return;
}
if (u <= l && r <= v) {
st[id] += val;
lazy[id] += val;
return;
}
int mid = (l + r) >> 1;
push (id, l, r);
upd (id * 2, l, mid, u, v, val);
upd (id * 2 + 1, mid + 1, r, u, v, val);
st[id] = st[id * 2] + st[id * 2 + 1];
return;
}
int get (int id, int l, int r, int u, int v) {
if (v < l || u > r) {
return 0;
}
if (u <= l && r <= v) {
return st[id];
}
int mid = (l + r) >> 1;
push (id, l, r);
int tL = get (id * 2, l, mid, u, v);
int tR = get (id * 2 + 1, mid + 1, r, u, v);
return (tL + tR);
}
};
int n, m;
int a[maxN];
pii off[maxN];
ST T;
void print (int lim) {
cout << "print\n";
for (int i = 1; i <= lim; i ++) {
cout << T.get (1, 1, lim, i, i) << ' ';
}
cout << '\n';
}
void solve () {
cin >> n >> m;
vector <int> zip;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
zip.push_back (a[i]);
}
for (int i = 1; i <= m; i ++) {
int t;
cin >> t;
if (t == 1) {
int b;
cin >> b;
off[i] = {b, -1};
zip.push_back (b);
}
else {
int c, d;
cin >> c >> d;
off[i] = {c, d};
zip.push_back (d);
}
}
sort (all (zip));
zip.erase (unique (all (zip)), zip.end ());
for (int i = 1; i <= n; i ++) {
a[i] = lower_bound (all (zip), a[i]) - zip.begin () + 1;
//cout << a[i] << '\n';
}
for (int i = 1; i <= m; i ++) {
if (off[i].se == -1) {
off[i].fi = lower_bound (all (zip), off[i].fi) - zip.begin () + 1;
//cout << 1 << ' ' << off[i].fi << '\n';
}
else {
off[i].se = lower_bound (all (zip), off[i].se) - zip.begin () + 1;
//cout << 2 << ' ' << off[i].fi << ' ' << off[i].se << '\n';
}
}
int lim = sz (zip) + 2;
T.init (lim);
for (int i = 1; i <= n; i ++) {
T.upd (1, 1, lim, 1, a[i], 1);
if (i >= 2) {
T.upd (1, 1, lim, 1, min (a[i], a[i - 1]), -1);
}
}
for (int j = 1; j <= m; j ++) {
if (off[j].se == -1) {
cout << T.get (1, 1, lim, off[j].fi, off[j].fi) << '\n';
}
else {
//print (lim);
auto [i, val] = off[j];
T.upd (1, 1, lim, 1, a[i], -1);
//print (lim);
if (i <= n - 1) {
T.upd (1, 1, lim, 1, min (a[i], a[i + 1]), 1);
}
//print (lim);
if (i >= 2) {
T.upd (1, 1, lim, 1, min (a[i], a[i - 1]), 1);
}
//print (lim);
a[i] = val;
T.upd (1, 1, lim, 1, a[i], 1);
// print (lim);
if (i <= n - 1) {
T.upd (1, 1, lim, 1, min (a[i], a[i + 1]), -1);
//print (lim);
}
if (i >= 2) {
T.upd (1, 1, lim, 1, min (a[i], a[i - 1]), -1);
//print (lim);
}
}
}
return;
}
signed main () {
cin.tie (nullptr) -> sync_with_stdio (false);
if (fopen (task".inp", "r")) {
freopen (task".inp", "r", stdin);
freopen (task".out", "w", stdout);
}
int t = 1;
//cin >> t;
while (t --) {
solve ();
}
return 0;
}
// thfv
