#include <algorithm> #include <array> #include <cassert> #include <deque> #include <functional> #include <iostream> #include <cstring> #include <ctime> #include <chrono> #include <numeric> #include <queue> #include <set> #include <vector> #include <random> #define LOCAL using namespace std; // #ifdef LOCAL // #include "debug.h" // #else // #define debug(...) 42 // #endif typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<pii> vpii; #define all(x) (x).begin(), (x).end() #define isz(x) (int)(x.size()) #define int ll mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); const int sz = 1e5+100, inf = 1000000000; const ll mod = 1000000007, INF = 1000000000000000000; struct BIT { int n; vi ft; void init(int _n){ ft.assign(_n+10, 0); n = _n; } void update(int x, int val) { for (;x <= n; x += x & -x) ft[x] += val; } int getans(int x) { int sum = 0; for (;x > 0; x -= x & -x) sum += ft[x]; return sum; } int sum(int l, int r) { return getans(r) - getans(l - 1); } void updateRange(int l, int r, int val) { update(l, val); update(r+1, -val); } }; int a[sz]; void solve() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; } BIT ft; ft.init(1e6+100); for (int i = 1; i < n; i++) { int x = a[i]; int y = a[i+1]; if (x > y) swap(x, y); ft.updateRange(x, y, 1); } while (m--) { int t; cin >> t; if (t == 1) { int pos, x; cin >> pos >> x; if (pos > 1) { int A = a[pos]; int B = a[pos-1]; if (A > B) swap(A, B); ft.updateRange(A, B, -1); A = x; if (A > B) swap(A, B); ft.updateRange(A, B, +1); } if (pos < n) { int A = a[pos]; int B = a[pos+1]; if (A > B) swap(A, B); ft.updateRange(A, B, -1); A = x; if (A > B) swap(A, B); ft.updateRange(A, B, +1); } a[pos] = x; } else { int h; cin >> h; cout << ft.getans(h) << '\n'; } } } void precompute() {} signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); #ifdef LOCAL // freopen("err.log", "w", stderr); // freopen("game.out", "w", stdout); // freopen("game.in", "r", stdin); #endif precompute(); solve(); }