#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
constexpr int MAXV = int(5E6);
struct node {
int sum;
int lv;
int rv;
node() {}
node(int a, int b, int c) : sum(a), lv(b), rv(c) {}
node(const node& x) : sum(x.sum), lv(x.lv), rv(x.rv) {}
} tree[MAXV];
int node_alloc;
int new_node() {
tree[node_alloc] = {0, -1, -1};
return node_alloc++;
}
int new_node(int x) {
tree[node_alloc] = tree[x];
return node_alloc++;
}
int init(int l, int r) {
if (l == r) {
return new_node();
}
int v = new_node();
int mid = (l + r) >> 1;
tree[v].lv = init(l, mid);
tree[v].rv = init(mid + 1, r);
return v;
}
int modify(int v, int l, int r, int p) {
if (l == r) {
int nv = new_node(v);
tree[nv].sum++;
return nv;
}
int mid = (l + r) >> 1;
int nv = new_node(v);
if (p <= mid) {
tree[nv].lv = modify(tree[v].lv, l, mid, p);
tree[nv].sum++;
} else {
tree[nv].rv = modify(tree[v].rv, mid + 1, r, p);
tree[nv].sum++;
}
return nv;
}
int query(int v, int l, int r, int ql, int qr) {
if (ql == l && r == qr) {
return tree[v].sum;
}
int mid = (l + r) >> 1;
if (qr <= mid) {
return query(tree[v].lv, l, mid, ql, qr);
} else if (mid + 1 <= ql) {
return query(tree[v].rv, mid + 1, r, ql, qr);
} else {
return query(tree[v].lv, l, mid, ql, mid)
+ query(tree[v].rv, mid + 1, r, mid + 1, qr);
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, Q;
std::cin >> N >> Q;
std::vector<int> A(N);
for (int i = 0; i < N; ++i) {
std::cin >> A[i];
}
std::vector<int> vals(A.begin(), A.end());
std::vector<std::array<int, 3>> qq(Q);
for (int i = 0; i < Q; ++i) {
std::cin >> qq[i][0];
if (qq[i][0] == 1) {
std::cin >> qq[i][1] >> qq[i][2];
--qq[i][1];
vals.emplace_back(qq[i][2]);
} else {
std::cin >> qq[i][1];
vals.emplace_back(qq[i][1]);
}
}
vals.emplace_back(-1);
int nvals;
std::sort(vals.begin(), vals.end());
vals.resize(nvals = int(std::unique(vals.begin(), vals.end()) - vals.begin()));
for (int i = 0; i < N; ++i) {
A[i] = std::lower_bound(vals.begin(), vals.end(), A[i]) - vals.begin();
}
for (int i = 0; i < Q; ++i) {
if (qq[i][0] == 1) {
qq[i][2] = std::lower_bound(vals.begin(), vals.end(), qq[i][2]) - vals.begin();
} else {
qq[i][1] = std::lower_bound(vals.begin(), vals.end(), qq[i][1]) - vals.begin();
}
}
debug("wtf");
constexpr int B = 317;
std::vector<int> roots(nvals + 1);
auto construct = [&]() -> void {
node_alloc = 0;
std::vector<std::pair<int, int>> piivec;
for (int i = 0; i + 1 < N; ++i) {
piivec.emplace_back(std::min(A[i], A[i + 1]), std::max(A[i], A[i + 1]));
}
std::sort(piivec.begin(), piivec.end());
roots[0] = init(0, nvals - 1);
int pivot = 0;
for (int i = 0; i < nvals; ++i) {
roots[i + 1] = roots[i];
while (pivot < piivec.size() && piivec[pivot].first == i) {
roots[i + 1] = modify(roots[i + 1], 0, nvals - 1, piivec[pivot].second);
pivot++;
}
}
};
std::vector<std::tuple<int, int, int>> changed;
for (int l = 0; l < Q; l += B) {
int r = std::min(Q, l + B);
changed.clear();
debug(l, r);
construct();
debug("???");
for (int i = l; i < r; ++i) {
if (qq[i][0] == 1) {
for (int idx : {qq[i][1] - 1, qq[i][1]}) {
if (0 <= idx && idx + 1 < N) {
changed.emplace_back(std::min(A[idx], A[idx + 1]), std::max(A[idx], A[idx + 1]), -1);
}
}
A[qq[i][1]] = qq[i][2];
for (int idx : {qq[i][1] - 1, qq[i][1]}) {
if (0 <= idx && idx + 1 < N) {
changed.emplace_back(std::min(A[idx], A[idx + 1]), std::max(A[idx], A[idx + 1]), +1);
}
}
} else {
int ans = query(roots[qq[i][1]], 0, nvals - 1, qq[i][1], nvals - 1);
debug(ans);
for (auto[x, y, d] : changed) {
if (x < qq[i][1] && qq[i][1] < y) {
ans += d;
}
}
std::cout << ans << '\n';
}
}
}
return 0;
}
